```
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:

- if
**n<3**then the number of primes is**0**(0 and 1 are not primes) - create an array of boolean of length
**n** **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)- starting from int
**i=2**take this number as the smallest prime - 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--**). - take the
**next i**in the sequence that is**not marked**and repeat the

process from point 5. - 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).