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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Count of Numbers Which Are Not Special

Number: 3507

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two positive integers l and r, a number is defined as special if it has exactly 2 proper divisors (i.e., all positive divisors except the number itself). For example, 4 (with proper divisors 1 and 2) is special, while 6 (with proper divisors 1, 2, and 3) is not. The 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 has exactly 2 proper divisors.
  • The number of divisors of any number x includes 1 and x itself. So if a number x has exactly 3 total divisors, then its proper divisors count is 2.
  • The only numbers with exactly 3 total divisors are perfect squares of prime numbers. (For a prime p, p^2 has divisors: 1, p, and p^2.)
  • Therefore, the special numbers in the range [l, r] are exactly the numbers of the form p^2, where p is prime and p^2 lies in [l, r].
  • The answer can be computed by subtracting the count of special numbers from the total number of numbers in the interval.

Space and Time Complexity

Time Complexity: O(√(r)) mainly from the Sieve to generate primes up to √(r). Space Complexity: O(√(r)) for storing the sieve.

Solution

The solution works as follows:

  1. Calculate lowBound as ceil(sqrt(l)) and highBound as floor(sqrt(r)). These represent the range for candidate primes p such that p^2 is within [l, r].
  2. Use a Sieve of Eratosthenes to generate all primes up to highBound.
  3. Count the primes that lie in the interval [lowBound, highBound]. Each such prime gives a special number (its square).
  4. Compute the total numbers in [l, r] which is (r - l + 1) and subtract the count of special numbers to obtain the count of numbers that are not special.
  5. Edge cases: when l or r are such that no p^2 falls within the range, the count of special numbers is zero.

The chosen data structures include an array (or list) for the sieve. The algorithmic approach efficiently counts primes up to √(r), ensuring that even for large values of r (up to 10^9) the solution remains efficient.

Code Solutions

# Python Solution

import math

def count_not_special(l, r):
    # Calculate lower and upper bounds for prime p such that p^2 is in range [l, r]
    lower_bound = math.ceil(math.sqrt(l))
    upper_bound = math.floor(math.sqrt(r))
    
    if lower_bound > upper_bound:
        # There are no primes p where p^2 lies in [l, r]
        return (r - l + 1)
    
    # Sieve of Eratosthenes to compute primes up to upper_bound
    sieve = [True] * (upper_bound + 1)
    sieve[0] = sieve[1] = False  # 0 and 1 are not prime
    for i in range(2, int(upper_bound ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * i, upper_bound + 1, i):
                sieve[j] = False
    
    # Count primes in the interval [lower_bound, upper_bound]
    special_count = sum(1 for p in range(lower_bound, upper_bound + 1) if sieve[p])
    
    # Total numbers in [l, r]
    total_numbers = r - l + 1
    # Count of numbers that are not special
    not_special_count = total_numbers - special_count
    return not_special_count

# Example Usage:
# For l = 4, r = 16, expected output is 11 (special numbers: 4 and 9)
print(count_not_special(4, 16))
← Back to All Questions