# Count Prime (204)

**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.&#x20;

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

**`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](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).&#x20;

* 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.

```java
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.