# Find the Count of Numbers Which Are Not Special
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-count-of-numbers-which-are-not-special)
Canonical: https://scaleengineer.com/dsa/problems/find-the-count-of-numbers-which-are-not-special
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## 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**.

**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 <= 109`

# Approaches
## Brute-Force by Counting Divisors
This approach directly implements the definition from the problem description. We iterate through every number `x` in the given range `[l, r]`. For each number, we find all its proper divisors and count them. If the count is exactly 2, we classify the number as special. Finally, we subtract the count of special numbers from the total number of elements in the range to get the result.
**Time:** O((r - l) * r). The outer loop runs `r - l + 1` times. The inner `isSpecial` function takes O(n) time for each number `n`. In the worst case, this is `O((r - l) * r)`. This is too slow for the given constraints. · **Space:** O(1), as we only use a few variables to store counts, requiring constant extra space.
**Pros:** Simple to understand and implement directly from the problem definition.
**Cons:** Extremely inefficient due to its high time complexity.; Will result in a Time Limit Exceeded (TLE) error for the given constraints.
### Explanation
The core idea is to check each number individually based on the definition of a special number. A number is special if it has exactly two proper divisors. The algorithm iterates from `l` to `r`, and for each number, it performs another iteration from 1 up to the number itself to count its proper divisors. If the count of proper divisors is two, the number is counted as special. The total count of non-special numbers is then the size of the range minus the count of special numbers found.

```java
class Solution {
    public int nonSpecialCount(int l, int r) {
        int specialCount = 0;
        for (int x = l; x <= r; x++) {
            if (isSpecial(x)) {
                specialCount++;
            }
        }
        return (r - l + 1) - specialCount;
    }

    private boolean isSpecial(int n) {
        if (n <= 3) { // Numbers 1, 2, 3 have less than 2 proper divisors
            return false;
        }
        int properDivisorCount = 0;
        // A simple optimization is to loop up to n/2
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                properDivisorCount++;
            }
        }
        return properDivisorCount == 2;
    }
}
```
### Algorithm
- The total number of integers in the range `[l, r]` is `r - l + 1`.
- We can find the number of non-special numbers by calculating `(total numbers) - (special numbers)`.
- To find the count of special numbers:
  1. Initialize a counter `specialCount` to 0.
  2. Loop through each integer `x` from `l` to `r`.
  3. For each `x`, find the number of its proper divisors.
     - Initialize a `divisorCount` to 0.
     - Loop with a variable `i` from 1 to `x - 1`.
     - If `x` is divisible by `i` (`x % i == 0`), increment `divisorCount`.
  4. If `divisorCount` is exactly 2, it means `x` is a special number. Increment `specialCount`.
  5. After checking all numbers from `l` to `r`, the final answer is `(r - l + 1) - specialCount`.

## Iteration with Optimized Special Number Check
This approach improves upon the brute-force method by using a key mathematical property of special numbers. A number is special if and only if it is the square of a prime number. Instead of counting all proper divisors, for each number `x` in the range `[l, r]`, we first check if it's a perfect square. If it is, we then check if its square root is a prime number. This check is significantly faster than counting all divisors.
**Time:** O((r - l) * r^(1/4)). The outer loop runs `r - l + 1` times. For each number `x`, the primality test on its square root `s` takes `O(sqrt(s)) = O(sqrt(sqrt(x))) = O(x^(1/4))` time. This is still too slow if the range `r - l` is large. · **Space:** O(1). No significant extra space is used besides a few variables for calculation.
**Pros:** More efficient than the first approach by using a mathematical insight.; Correctly identifies the structure of special numbers.
**Cons:** Still inefficient for large ranges where `r - l` is large.; Will likely result in a Time Limit Exceeded (TLE) error if the range is not small.
### Explanation
By understanding that special numbers are squares of primes, we can optimize the check. The algorithm iterates through each number `x` from `l` to `r`. For each `x`, it calculates `s = sqrt(x)`. If `x` is not a perfect square (i.e., `s*s != x`), it cannot be special. If it is a perfect square, we then need to verify if the root `s` is a prime number. A standard primality test for `s` involves checking for divisors up to `sqrt(s)`. This avoids the slow process of counting all divisors for `x`.

```java
class Solution {
    public int nonSpecialCount(int l, int r) {
        int specialCount = 0;
        for (int x = l; x <= r; x++) {
            if (isSpecial(x)) {
                specialCount++;
            }
        }
        return (r - l + 1) - specialCount;
    }

    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    private boolean isSpecial(int n) {
        if (n <= 3) return false;
        int s = (int) Math.sqrt(n);
        if (s * s != n) {
            return false;
        }
        return isPrime(s);
    }
}
```
### Algorithm
- First, we deduce the mathematical property of special numbers. A number `x` is special if it has 2 proper divisors, meaning it has 3 total divisors. A number has an odd number of divisors if and only if it is a perfect square. For the number of divisors to be exactly 3 (a prime number), the number must be of the form `p^2`, where `p` is a prime number.
- The algorithm is as follows:
  1. Initialize `specialCount` to 0.
  2. Iterate through each number `x` from `l` to `r`.
  3. For each `x`, check if it's a special number:
     a. Calculate the integer square root, `s = (int) Math.sqrt(x)`.
     b. If `s * s == x` (i.e., `x` is a perfect square), proceed to check if `s` is prime.
     c. To check if `s` is prime, use a helper function `isPrime(s)` that checks for divisibility from 2 up to `sqrt(s)`.
     d. If `x` is a perfect square and its root `s` is prime, increment `specialCount`.
  4. The final result is `(r - l + 1) - specialCount`.

## Pre-computation using Sieve of Eratosthenes
This is the most efficient approach. Instead of checking every number in the potentially vast range `[l, r]`, we generate all the special numbers and count how many fall within the range. Since special numbers are squares of primes (`p^2`), we only need to find primes `p` such that `p^2 <= r`. The most effective way to find all primes up to a certain limit (here, `sqrt(r)`) is the Sieve of Eratosthenes. After finding the primes, we square them and check if they are in `[l, r]`.
**Time:** O(sqrt(r) * log(log(sqrt(r)))). The Sieve of Eratosthenes runs in `O(N * log(log(N)))` where `N = sqrt(r)`. The final loop to count special numbers runs up to `sqrt(r)`. The dominant part is the sieve. This is very efficient and passes the time limits. · **Space:** O(sqrt(r)). We need a boolean array of size `sqrt(r) + 1` for the sieve. Given `r <= 10^9`, this is `O(31623)`, which is perfectly acceptable.
**Pros:** Highly efficient and optimal for the given constraints.; Avoids iterating over the potentially very large range `[l, r]`.
**Cons:** Requires knowledge of prime number generation algorithms like the Sieve of Eratosthenes.; Slightly more complex to implement than the naive approaches.
### Explanation
The optimal strategy is to change the perspective: instead of checking numbers, we generate the numbers that fit the criteria. We need to count `p^2` where `p` is prime and `l <= p^2 <= r`. This means we only need to find primes up to `sqrt(r)`. Since `r <= 10^9`, `sqrt(r)` is at most `31622`, which is a small number.

We can use the Sieve of Eratosthenes to pre-compute all primes up to `sqrt(r)`. Once we have the list of primes, we iterate through them, square each prime, and check if the result is within the `[l, r]` interval. This avoids iterating over the large `[l, r]` range entirely.

```java
import java.util.Arrays;

class Solution {
    public int nonSpecialCount(int l, int r) {
        int limit = (int) Math.sqrt(r);
        boolean[] isPrime = new boolean[limit + 1];
        Arrays.fill(isPrime, true);
        
        if (limit >= 0) isPrime[0] = false;
        if (limit >= 1) isPrime[1] = false;

        for (int p = 2; p * p <= limit; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= limit; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        int specialCount = 0;
        for (int p = 2; p <= limit; p++) {
            if (isPrime[p]) {
                long specialNum = (long) p * p;
                if (specialNum >= l && specialNum <= r) {
                    specialCount++;
                }
            }
        }

        return (r - l + 1) - specialCount;
    }
}
```
### Algorithm
- The key insight is to generate the special numbers themselves, rather than testing each number in the `[l, r]` range.
- A number `x` is special if `x = p^2` for some prime `p`.
- We need to find primes `p` such that `l <= p^2 <= r`. The maximum prime we need to consider is `p <= sqrt(r)`.
- The algorithm is as follows:
  1. Calculate the upper bound for our prime search: `limit = (int) Math.sqrt(r)`.
  2. Use the Sieve of Eratosthenes to generate all prime numbers up to `limit`.
     a. Create a boolean array `isPrime` of size `limit + 1` and initialize all entries to `true`.
     b. Mark `isPrime[0]` and `isPrime[1]` as `false`.
     c. Iterate from `p = 2` up to `sqrt(limit)`. If `isPrime[p]` is `true`, then iterate through its multiples `j = p * p` to `limit` and mark `isPrime[j]` as `false`.
  3. Initialize `specialCount = 0`.
  4. Iterate from `p = 2` up to `limit`.
  5. If `isPrime[p]` is `true`, calculate its square: `specialNum = (long) p * p`.
  6. Check if this special number falls within our range: `if (specialNum >= l && specialNum <= r)`.
  7. If it does, increment `specialCount`.
  8. The final answer is `(r - l + 1) - specialCount`.

# Solutions
### Java

```java
class Solution {
  static int m = 31623;
  static boolean[] primes = new boolean[m + 1];
  static {
    Arrays.fill(primes, true);
    primes[0] = primes[1] = false;
    for (int i = 2; i <= m; i++) {
      if (primes[i]) {
        for (int j = i + i; j <= m; j += i) {
          primes[j] = false;
        }
      }
    }
  }
public
  int nonSpecialCount(int l, int r) {
    int lo = (int)Math.ceil(Math.sqrt(l));
    int hi = (int)Math.floor(Math.sqrt(r));
    int cnt = 0;
    for (int i = lo; i <= hi; i++) {
      if (primes[i]) {
        cnt++;
      }
    }
    return r - l + 1 - cnt;
  }
}

```

### CPP

```cpp
const int m = 31623 ; bool primes [ m + 1 ]; auto init = [] { memset ( primes , true , sizeof ( primes )); primes [ 0 ] = primes [ 1 ] = false ; for ( int i = 2 ; i <= m ; ++ i ) { if ( primes [ i ]) { for ( int j = i * 2 ; j <= m ; j += i ) { primes [ j ] = false ; } } } return 0 ; }(); class Solution { public: int nonSpecialCount ( int l , int r ) { int lo = ceil ( sqrt ( l )); int hi = floor ( sqrt ( r )); int cnt = 0 ; for ( int i = lo ; i <= hi ; ++ i ) { if ( primes [ i ]) { ++ cnt ; } } return r - l + 1 - cnt ; } };
```

### Python

```python
m = 31623 primes = [ True ] * ( m + 1 ) primes [ 0 ] = primes [ 1 ] = False for i in range ( 2 , m + 1 ): if primes [ i ]: for j in range ( i + i , m + 1 , i ): primes [ j ] = False class Solution : def nonSpecialCount ( self , l : int , r : int ) -> int : lo = ceil ( sqrt ( l )) hi = floor ( sqrt ( r )) cnt = sum ( primes [ i ] for i in range ( lo , hi + 1 )) return r - l + 1 - cnt
```