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.

Examples

Example 1

Input: l = 5, r = 7

Output: 3

Explanation:

There are no special numbers in the range `[5, 7]`.

Example 2

Input: l = 4, r = 16

Output: 11

Explanation:

The special numbers in the range `[4, 16]` are 4 and 9.

Constraints

• 1 <= l <= r <= 10^9

Solution

Method 1 – Count All, Subtract Special (Brute Force for Small Range)

Intuition

A number is special if it has exactly 2 proper divisors, i.e., it is the square of a prime (since divisors are 1, p, and p^2). So, for each prime p, p^2 is special. We count all such numbers in [l, r] and subtract from the total.

Approach

1. Count the total numbers in [l, r].
2. For each prime p such that p^2 is in [l, r], count p^2 as special.
3. Subtract the count of special numbers from the total.
4. Return the result.

Code

C++

class Solution {
public:
    int countNotSpecial(int l, int r) {
        int ans = r - l + 1;
        vector<bool> is_prime(1e6+1, true);
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i * i <= r; ++i) {
            if (is_prime[i]) {
                for (int j = i * 2; j * j <= r; j += i) is_prime[j] = false;
            }
        }
        for (int i = 2; i * i <= r; ++i) {
            if (is_prime[i]) {
                int sq = i * i;
                if (sq >= l && sq <= r) --ans;
            }
        }
        return ans;
    }
};

Go

func countNotSpecial(l, r int) int {
    ans := r - l + 1
    isPrime := make([]bool, 1_000_001)
    for i := range isPrime { isPrime[i] = true }
    isPrime[0], isPrime[1] = false, false
    for i := 2; i*i <= r; i++ {
        if isPrime[i] {
            for j := i * 2; j*j <= r; j += i {
                isPrime[j] = false
            }
        }
    }
    for i := 2; i*i <= r; i++ {
        if isPrime[i] {
            sq := i * i
            if sq >= l && sq <= r {
                ans--
            }
        }
    }
    return ans
}

Java

class Solution {
    public int countNotSpecial(int l, int r) {
        int ans = r - l + 1;
        boolean[] isPrime = new boolean[1_000_001];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= r; ++i) {
            if (isPrime[i]) {
                for (int j = i * 2; j * j <= r; j += i) isPrime[j] = false;
            }
        }
        for (int i = 2; i * i <= r; ++i) {
            if (isPrime[i]) {
                int sq = i * i;
                if (sq >= l && sq <= r) --ans;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun countNotSpecial(l: Int, r: Int): Int {
        var ans = r - l + 1
        val isPrime = BooleanArray(1_000_001) { true }
        isPrime[0] = false; isPrime[1] = false
        for (i in 2..r) {
            if (i * i > r) break
            if (isPrime[i]) {
                var j = i * 2
                while (j * j <= r) {
                    isPrime[j] = false
                    j += i
                }
            }
        }
        for (i in 2..r) {
            if (i * i > r) break
            if (isPrime[i]) {
                val sq = i * i
                if (sq in l..r) ans--
            }
        }
        return ans
    }
}

Python

class Solution:
    def countNotSpecial(self, l: int, r: int) -> int:
        ans = r - l + 1
        is_prime = [True] * (10**6 + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(r**0.5) + 1):
            if is_prime[i]:
                for j in range(i*2, int(r**0.5) + 1, i):
                    is_prime[j] = False
        for i in range(2, int(r**0.5) + 1):
            if is_prime[i]:
                sq = i * i
                if l <= sq <= r:
                    ans -= 1
        return ans

Rust

impl Solution {
    pub fn count_not_special(l: i32, r: i32) -> i32 {
        let mut ans = r - l + 1;
        let mut is_prime = vec![true; 1_000_001];
        is_prime[0] = false;
        is_prime[1] = false;
        let r_sqrt = (r as f64).sqrt() as i32;
        for i in 2..=r_sqrt {
            if is_prime[i as usize] {
                let mut j = i * 2;
                while j <= r_sqrt {
                    is_prime[j as usize] = false;
                    j += i;
                }
            }
        }
        for i in 2..=r_sqrt {
            if is_prime[i as usize] {
                let sq = i * i;
                if sq >= l && sq <= r {
                    ans -= 1;
                }
            }
        }
        ans
    }
}

TypeScript

class Solution {
    countNotSpecial(l: number, r: number): number {
        let ans = r - l + 1;
        const isPrime = Array(1_000_001).fill(true);
        isPrime[0] = isPrime[1] = false;
        for (let i = 2; i * i <= r; ++i) {
            if (isPrime[i]) {
                for (let j = i * 2; j * j <= r; j += i) isPrime[j] = false;
            }
        }
        for (let i = 2; i * i <= r; ++i) {
            if (isPrime[i]) {
                const sq = i * i;
                if (sq >= l && sq <= r) --ans;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(√r log log r), for the sieve and checking squares.
• 🧺 Space complexity: O(√r), for the sieve array.