We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Count of Numbers Which Are Not Special

Difficulty: Medium

Problem Description

You are given 2 positive integers l and r. A number is called special if it has exactly 2 proper divisors. Your task is to return the count of numbers in the range [l, r] that are not special.

Key Insights

  • A number is special if it can be expressed as the square of a prime number (since it will have exactly three divisors: 1, p, and p^2).
  • The challenge is to identify the prime numbers whose squares fall within the range [l, r].
  • The total count of numbers in the range can be derived straightforwardly as r - l + 1.
  • The count of special numbers can be determined by counting the prime squares within [l, r].

Space and Time Complexity

Time Complexity: O(√r log log √r) - for generating primes up to √r using the Sieve of Eratosthenes. Space Complexity: O(√r) - for storing the primes up to √r.

Solution

To solve this problem, we can use the Sieve of Eratosthenes to find all prime numbers up to √r. For each prime number p, we compute p^2 and check if it lies within the range [l, r]. The total count of numbers in the range is r - l + 1, and we subtract the count of special numbers (those which are prime squares) from this total.

Code Solutions

def count_not_special(l: int, r: int) -> int:
    import math

    def sieve_of_eratosthenes(n):
        is_prime = [True] * (n + 1)
        p = 2
        while (p * p <= n):
            if (is_prime[p]):
                for i in range(p * p, n + 1, p):
                    is_prime[i] = False
            p += 1
        return [p for p in range(2, n + 1) if is_prime[p]]

    # Find all primes up to sqrt(r)
    limit = int(math.sqrt(r))
    primes = sieve_of_eratosthenes(limit)

    # Count special numbers
    special_count = 0
    for prime in primes:
        prime_square = prime * prime
        if l <= prime_square <= r:
            special_count += 1

    # Total numbers in range [l, r]
    total_count = r - l + 1
    return total_count - special_count
← Back to All Questions