Find the Count of Numbers Which Are Not Special - Problem

You are given 2 positive integers l and r.

For any number x, all positive divisors of x except x are called the proper divisors of x.

A number is called special if it has exactly 2 proper divisors.

For example:

The number 4 is special because it has proper divisors 1 and 2.
The number 6 is not special because it has proper divisors 1, 2, and 3.

Return the count of numbers in the range [l, r] that are not special.

Input & Output

Example 1 — Basic Range

$ Input: l = 5, r = 7

› Output: 3

💡 Note: Numbers 5, 6, 7: None are special (5 has 1 proper divisor, 6 has 3 proper divisors, 7 has 1 proper divisor), so all 3 are not special

Example 2 — Including Special Number

$ Input: l = 4, r = 16

› Output: 11

💡 Note: Range has 13 numbers total. Special numbers: 4 (divisors 1,2), 9 (divisors 1,3), 16 (divisors 1,2,4,8) - wait, 16 has 4 proper divisors, only 4 and 9 are special. Non-special count: 13 - 2 = 11

Example 3 — No Special Numbers

$ Input: l = 10, r = 15

› Output: 6

💡 Note: Numbers 10,11,12,13,14,15: None are squares of primes, so all 6 numbers are not special

Constraints

1 ≤ l ≤ r ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 18

The key insight is that special numbers (having exactly 2 proper divisors) are squares of prime numbers. Best approach uses Sieve of Eratosthenes to find primes up to √r, then counts their squares in range [l,r]. Time: O(√r log log √r), Space: O(√r)

Common Approaches

✓ Dp 2d

⏱️ Time: N/A Space: N/A

Brute Force - Check Each Number

⏱️ Time: O((r-l+1) × max(r)) Space: O(1)

For every number from l to r, find all its proper divisors by checking every number from 1 to n-1. Count proper divisors and check if exactly 2. Count numbers that are not special.

Mathematical Pattern Recognition

⏱️ Time: O(sqrt(r) × log(log(sqrt(r)))) Space: O(sqrt(r))

Key insight: A number has exactly 2 proper divisors if and only if it's the square of a prime number. We use Sieve of Eratosthenes to find all primes up to sqrt(r), then count their squares in range [l,r].

Optimized Divisor Counting

⏱️ Time: O((r-l+1) × sqrt(max(r))) Space: O(1)

Instead of checking all numbers up to n-1, we only check up to sqrt(n) and count pairs of divisors. This significantly reduces the number of operations per number.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int intSqrt(int n) {
    if (n == 0) return 0;
    int x = n;
    int y = (x + 1) / 2;
    while (y < x) {
        x = y;
        y = (x + n / x) / 2;
    }
    return x;
}

int solution(int l, int r) {
    // Find all primes up to sqrt(r) using sieve
    int limit = intSqrt(r) + 1;
    bool isPrime[100001];
    for (int i = 0; i <= limit; i++) {
        isPrime[i] = true;
    }
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // Count special numbers (squares of primes) in range [l, r]
    int specialCount = 0;
    for (int i = 2; i <= limit; i++) {
        if (isPrime[i]) {
            long long square = (long long)i * i;
            if (square >= l && square <= r) {
                specialCount++;
            }
        }
    }
    
    // Return count of non-special numbers
    return (r - l + 1) - specialCount;
}

int main() {
    int l, r;
    scanf("%d", &l);
    scanf("%d", &r);
    
    int result = solution(l, r);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

30.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen