# My simple Java 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] == false) {
count++;
for (int j = 2; i*j < n; j++) {
notPrime[i*j] = true;
}
}
}

return count;
}
}``````

• Do you mined explaining me the purpose of making 'notPrime' array true by multiplying 'i' and 'j'. I'm unable to understand the logic behind. Thanks

• it starts from 2, the first prime, then mark the multip of 2 as true in notPrime, so the loop of i will skip them. the next prime is 3, do the same thing. Then it is 4, which 2*2, so the not prime is true, and will skip to next.

• this video is great!Thanks!

• 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;
}``````

• Sieve of Eratosthenes Ladies and Gents. Awesome code man.

• Nice solution!
But instead of i++ here 'i' could be updated to next prime by finding next 'false' value in notPrime[]. This would optimize the code a bit.

• what is the time complexity of this ?
EDIT: Never mind, the hints have the details

• @chidong Will this optimization improve the run time in big O notation?

• @dryear no, but will, in reality.

• It seems that this code will cause overflow. Add a condition check to skip the inner for loop when `i > sqrt(n)` to avoid it.

``````......
count++;
if (i > Math.sqrt(n)) continue;
for (int j = 2; i*j < n; j++) {
notPrime[i*j] = true;
......``````

• This post is deleted!

• 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;
}
}
``````

• What would be the time complexity? Can we find a tighter bound to O(sqrt(n))?

• @Chidong anyway you're iterating O(n) to get the count

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