# [3233\. Find the Count of Numbers Which Are Not Special](https://leetcode.com/problems/find-the-count-of-numbers-which-are-not-special/)

:::spoiler Hint

class Solution {
public:
    int nonSpecialCount(int l, int r)
    {
        // Calculate the upper limit for prime number checking (sqrt(r))

        // Vector to mark prime numbers using the Sieve of Eratosthenes
        // 0 and 1 are not prime numbers

        // Sieve of Eratosthenes to mark non-prime numbers
        for ()
        {
            if ()
            {
                for ()
                {
                    // Mark multiples of i as non-prime
                }
            }
        }

        // Count the number of squares of primes within the range [l, r]
        for ()
        {
            if ()
            {
                // Calculate the square of the prime number
                if ()
                {
                    // Increment count if the square is within the range
                }
            }
        }

        // Calculate the total number of numbers in the range [l, r]

        // Return the number of non-special numbers
    }
};

:::

:::spoiler Solution

class Solution {
public:
    int nonSpecialCount(int l, int r)
    {
        int limit = (int)(sqrt(r));

        vector<bool> isPrime(limit + 1, true);
        isPrime[0] = isPrime[1] = false;

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

        int cnt = 0;
        for (int i = 2; i <= limit; i++)
        {
            if (isPrime[i])
            {
                int square = i * i;
                if (l <= square && square <= r)
                {
                    cnt++;
                }
            }
        }

        int total = r - l + 1;

        return total - cnt;        
    }
};

- T: $O(\sqrt r)$
- S: $O(\sqrt r)$
:::