package math;
public class CountPrimes {
//统计所有小于非负整数 n 的质数的数量。
/*
* 输入: 10
* 输出: 4
* 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7
*
* */
public int countPrimes(int n) {
if(n<=1)
return 0;
//默认所有的元素值都会设置为false
boolean[] notPrime = new boolean[n];
notPrime[0] = true;
notPrime[1] = true;
for (int i = 2; i * i < n; i++) {
if (!notPrime[i]) {
for (int j = 2 * i; j < n; j += i) {
notPrime[j] = true;
}
}
}
int result = 0;
for (boolean b : notPrime) {
if (!b) {
result++;
}
}
return result;
}
}
