//maybe time cost higher than Sieve of Eratosthenes, but only need to store primes, space cost is O(primes) rather than O(n)

//Idea is to check if N is prime, we only need to check whether N has the prime factors less than sqrt(N). Because if it has non-prime factor, it must has corresponding prime factor.

```
public class Solution {
public int countPrimes(int n) {
int count = 0;
List<Integer> primes = new ArrayList<Integer>();
for(int i=2;i<n;i++){
boolean isPrime = true;
for(int j=0;j<primes.size();j++){
if(primes.get(j)*primes.get(j)>i) break;
if(i%primes.get(j)==0){
isPrime = false;
break;
}
}
if(isPrime){
primes.add(i);
count++;
}
}
return count;
}
}
```