```
public class Solution {
public int countPrimes(int n) {
if(n<=1) return 0;
int curr = 2;
int count=0;
boolean flag[] = new boolean[n];
for(int i=2; i<n; i++){
flag[i]= true;
}
while(curr*curr <=n){
for(int i=curr*curr,j=0; (i+j*curr)<n; j++){
flag[i+j*curr]=false;
}
for(int i = curr+1 ; i<n; i++){
if(flag[i]==true){
curr = i;
break;
}
}
}
for(int i=1;i<n;i++){
if(flag[i])count++;
}
return count;
}
```

}