Find the Count of Numbers Which Are Not Special

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

Understanding the Visualization

Input Range

Given range [l, r] to check

Identify Special

Special numbers have exactly 2 proper divisors

Count Non-Special

Return total numbers minus special count

Key Takeaway

🎯 Key Insight: Special numbers are exactly the squares of prime numbers!

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

Approach	Time	Space	Notes
✓ Brute Force - Check Each Number	O((r-l+1) × max(r))	O(1)	For each number in range, count its proper divisors to determine if it's special
Optimized Divisor Counting	O((r-l+1) × sqrt(max(r)))	O(1)	Use mathematical insight: check divisors only up to sqrt(n) to count faster
Mathematical Pattern Recognition	O(sqrt(r) × log(log(sqrt(r))))	O(sqrt(r))	Special numbers are squares of primes - use Sieve of Eratosthenes to find primes efficiently

Brute Force - Check Each Number — Algorithm Steps

Iterate through each number from l to r
For each number, count proper divisors by checking all numbers from 1 to n-1
If proper divisors ≠ 2, increment non-special count

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Number 4

Count divisors: 1, 2 → exactly 2 proper divisors → special

Check Number 6

Count divisors: 1, 2, 3 → 3 proper divisors → not special

Count Result

Count all non-special numbers in range

Code -

solution.c — C

#include <stdio.h>

int countProperDivisors(int n) {
    int count = 0;
    for (int i = 1; i < n; i++) {
        if (n % i == 0) {
            count++;
        }
    }
    return count;
}

int solution(int l, int r) {
    int nonSpecialCount = 0;
    for (int num = l; num <= r; num++) {
        if (countProperDivisors(num) != 2) {
            nonSpecialCount++;
        }
    }
    return nonSpecialCount;
}

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

Time & Space Complexity

Time Complexity

⏱️

O((r-l+1) × max(r))

For each number in range, we check all potential divisors up to that number

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Each Number — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler