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.

class Solution {
public:
    int nonSpecialCount(int l, int r) {
        int sq = sqrt(r) + 1;
        vector<int> sieve(sq);
        for(int i = 2; i < sq; i++) {
            if(sieve[i]) continue;
            for(int j = i * i; j < sq; j += i) sieve[j] = 1;
        }
        int res = 0;
        for(int i = 2; i < sq; i++) {
            if(sieve[i]) continue;
            int po = i * i;
            if(l <= po and po <= r) res++;
        }
        return r - l + 1 - res;
    }
};