3233. Find the Count of Numbers Which Are Not Special

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

Solution:

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

class Solution {
    public int nonSpecialCount(int l, int r) {
        // Step 1: Generate a list of prime numbers up to sqrt(r)
        int maxPrime = (int) Math.sqrt(r) + 1;
        boolean[] isPrime = new boolean[maxPrime + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= maxPrime; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxPrime; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // Step 2: Generate special numbers which are squares of these primes
        List<Integer> specialNumbers = new ArrayList<>();
        for (int i = 2; i <= maxPrime; i++) {
            if (isPrime[i]) {
                int specialNumber = i * i;
                specialNumbers.add(specialNumber);
            }
        }

        // Step 3: Count special numbers within the range [l, r]
        int specialCount = 0;
        for (int specialNumber : specialNumbers) {
            if (specialNumber >= l && specialNumber <= r) {
                specialCount++;
            }
        }

        // Step 4: Calculate non-special numbers
        int totalCount = r - l + 1;
        int nonSpecialCount = totalCount - specialCount;

        return nonSpecialCount;
    }
}