題目:
計數(shù)質(zhì)數(shù)
解法:
申請一個大小為n的boolean 數(shù)組, 默認初始化為false. 然后從2開始遍歷, 遇到false, 則計數(shù)器加一. 凡是2的倍數(shù)的數(shù), 都是非質(zhì)數(shù), 標(biāo)記為true. 遇到false我們認為其為質(zhì)數(shù), 否則不是質(zhì)數(shù). 同上, 即可求得結(jié)果.
public int countPrimes(int n) {
int count = 0;
boolean[] primeArr = new boolean[n];
for(int i = 2; i < n; i++){
if(primeArr[i] == false){
count++;
for(int j = i; j < n; j += i){
primeArr[j] = true;
}
}
}
return count;
}
