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

1
2
3
4
5
6
7
8


Input: l = 5, r = 7

Output: 3

Explanation:

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

Example 2

1
2
3
4
5
6
7
8


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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.