Count Prime (204)

Count the number of prime numbers less than a non-negative number, n.

Approach1 : Naive

We know that a Prime number n is only divisble by 1 and n. We can check that by running a loop starting from k = 2 until k < n, if at at any point point there is a remainder when n divides k, n would not be a prime.

This will also work if you check till N/2. This in itself can also be further optimized.

Complexity: O(N) time and O(1) space.

Approach 2 : Sieve of Eratosthenes

A better and more efficent approach is to use the Sieve of Eratosthenes.

• Create a boolean array of size n.

• Each time we hit a prime, we have to launch a search through the rest of the array to "cross out" the multiples of that prime by setting them to false because we know they aren't prime (The Sieve of Erathostenes).

• When we're done with running the sieve algorithm, we create a variable count and run thorugh the boolean prime array and increase count if that element is true.

class Solution {
    public int countPrimes(int n) {
        boolean[]prime = new boolean[n];
        Arrays.fill(prime, true);
        
        for(int i = 2; i * i < n; i++){
            if(prime[i]){
                for(int j = i * i; j < n; j += i){
                    prime[j] = false;
                }
            }
        }
        int count = 0;
        for(int i = 2; i < n; i++){
            if(prime[i])
                count++;
        }
        return count;
    }
}

Complexity: O(nlog(log(n))) time and O(1) space.

the time complexity of "crossing out" is:

O(n) * O(1/2 + 1/3 + 1/5 + ... + 1/(last prime before n)) = O(n) * O(log(log(n))) = O(nlog(log(n)))

Thus, the nlog(log(n)) simply comes from the sum: n/2 + n/3 + n/5 + ... + n/(last prime before n) when we're crossing out numbers in the Sieve algorithm.