public class Solution {
public int countPrimes(int n) {
boolean[] notPrime = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrime[i] == false) {
count++;
for (int j = 2; i*j < n; j++) {
notPrime[i*j] = true;
}
}
}
return count;
}
}
My simple Java solution


This can optimize the solution a little bit, since actually checking up to Math.sqrt(n) is enough.
public int countPrimes(int n) { if(n <=1 ) return 0; boolean[] notPrime = new boolean[n]; notPrime[0] = true; notPrime[1] = true; for(int i = 2; i < Math.sqrt(n); i++){ if(!notPrime[i]){ for(int j = 2; j*i < n; j++){ notPrime[i*j] = true; } } } int count = 0; for(int i = 2; i< notPrime.length; i++){ if(!notPrime[i]) count++; } return count; }




It seems this part of code could be changed like this
if(Math.sqrt(n) < i) continue; for (int j = i; i*j < n; j++) { notPrime[i*j] = true; }
this could be called Sieve of Eratosthenes
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Similar solution, using
BitSet
:int countPrimes(int n) { BitSet compounds = new BitSet(n); for (int i = 2, end = (int) Math.sqrt(n); i <= end; i = compounds.nextClearBit(i + 1)) for (int j = i * i; j < n; j += i) compounds.set(j); return Math.max(0, n  (compounds.cardinality() + 2)); }

Great solution, just add one more line to decrease the unnecessary check.
public int countPrimes(int n) { boolean[] notPrime = new boolean[n]; int count=0; for(int i=2;i<n;i++) { if(!notPrime[i]) { count++; if(i*i<n) //check up to Math.sqrt(n) for(int j=2;i*j<n;j++) notPrime[i*j] = true; } } return count; }

seems faster solution
public class Solution { public int countPrimes(int n) { boolean[] notPrime = new boolean[n]; int count = 0; for (int i = 2; i < n; ++i) { if (!notPrime[i]) { count++; // add i < Math.sqrt(n) to avoid overflow for (int j = i * i; i < Math.sqrt(n) && j < n ; j += i) { notPrime[j] = true; } } } return count; } }
