public int countPrimes(int n) {

if (n <= 2)

return 0;

boolean[] flag = new boolean[n];

int i = 3;

int count = 1;

while (i <= Math.sqrt(n)){

if (!flag[i]){

count++;

int j = i;

while (i * j < n){

flag[i*j] = true;

j += 2;

}

}

i += 2;

}

while (i < n){

if (!flag[i])

count++;

i += 2;

}

return count;

}