# Beats 99.45% of submissions

• ``````public class Solution {
public int countPrimes(int n) {

if( n <=2) {
return 0;
}

int c= 1;

boolean isNotPrime[] = new boolean[n+1];

for(int i=3;i*i<=n;i=i+2) {

if(isNotPrime[i]) {

continue;
}

for(int j= i*i ;j<=n;j=j+2*i) {
isNotPrime[j] = true;
}

}

for(int i =3;i<n;i=i+2){

if(!isNotPrime[i]) {
c++;
}
}
return c;

}
}``````

• why does this way work? Is there any detailed explanations? Also what's the complexity?

• Could you explain why you use this three lines to judge prime?

``````for(int j= i*i ;j<=n;j=j+2*i) {
isNotPrime[j] = true;
}
``````

I have doubt with whether it can filter all the primes.

• Because j + i, j + 3i, j + 5i, ... are even numbers, which are not prime.

• Thank you. I got your idea.

• why does j start from i * i?

• May I ask what is the complexity of this algorithm since I really don't know how to analyze the complexity of the inner loop:

``````for (int j = i * i; i <= n; j = j + 2 * i)
``````

Thanks

• @pancheng1987

The if statement before where you couldn't understand has eliminated all even number(i start from 3). so, i*i=j is odd.

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