判断小于n数中素数的个数,如果用普通的判断方法会超时,这里使用筛选法。
具体请参考:http://blog.csdn.net/liukehua123/article/details/5482854
public class Solution {
public int countPrimes(int n) {
if(n <= 2)
return 0;
int count = 0;
boolean[] prime = new boolean[n+1];
for(int i=1; i<n+1; i++) {
if(i % 2 == 0) {
prime[i] = false;
}
else {
prime[i] = true;
}
}
for(int i=3; i<=Math.sqrt(n); i++) {
if(prime[i]) {
for(int j=2*i; j<n; j+=i) {
prime[j] = false;
}
}
}
for(int i=1; i<n; i++) {
if(prime[i]) {
count++;
}
}
return count;
}
}