```
public class Solution {
public int countPrimes(int n) {
ArrayList<Integer> primes = new ArrayList<Integer>();
if(n < 3){
return 0;
}
int count = 1;
primes.add(2); // first put 2 into the prime list
for(int i = 3; i < n; i = i+2){ // only the odds
if(isPrime(i,primes)){
primes.add(i);
count++;
}
}
return count;
}
private boolean isPrime(int i, ArrayList<Integer> primes){
if(i != 5 && i % 5 == 0){
return false;
}
int j = 0;
while(primes.get(j) <= Math.sqrt(i)){
/*only need to test the prime in the list which less than sqrt of i*/
if(i % primes.get(j) == 0){
return false;
}
j++;
}
return true;
}
}
```