# Simple Solution

• ``````    public static int countPrimes(int n) {
if(n<3) return 0;
boolean[] primes = new boolean[n];
int count = n-2; // 0 and 1 are not prime, 2 is the first prime
for(int i=2;i<n;i++) {
if(!primes[i])
for(int j=i+i;j<n;j+=i) if(!primes[j]) { primes[j]=true; count--; }
}
return count;
}
``````

This solution uses the Sieve of Eratosthenes:

1. if n<3 then the number of primes is 0 (0 and 1 are not primes)
2. create an array of boolean of length n
3. initialize the count of primes to n-2 (initially we consider all
primes except for 0 and 1 that we already said are not primes)
4. starting from int i=2 take this number as the smallest prime
5. mark all multiples of i smaller than n as not prime. Every time an element is
marked as true (that indicates is not a prime), decrement the prime
count (count--).
6. take the next i in the sequence that is not marked and repeat the
process from point 5.
7. at the end we will have in the count variable the number of primes (the
number of elements that are not marked in the inner loop).

• if n eqaul INT_MAX, you need 2*32 bits, about 4GB.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.