3233. Find the Count of Numbers Which Are Not Special

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
    }
};

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)$