統(tǒng)計(jì)所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量。
示例 1：
輸入：n = 10
輸出：4
解釋：小于 10 的質(zhì)數(shù)一共有 4 個(gè), 它們是 2, 3, 5, 7
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-primes
解題思路
用一個(gè)長度為n的布爾數(shù)組，記錄哪些數(shù)是合數(shù)
遍歷數(shù)字從2到n吊档，跳過合數(shù)，遇到素?cái)?shù)x計(jì)數(shù)加一
然后將2x, 3x, 4x, ...這些數(shù)字標(biāo)記為合數(shù)
代碼
class Solution {
public int countPrimes(int n) {
int count = 0;
boolean[] isComposite = new boolean[n]; // 初始默認(rèn)false, 全部是素?cái)?shù)
for (int i = 2; i < n; i++) {
if (isComposite[i]) { // 跳過合數(shù)
continue;
}
count++; // 素?cái)?shù) + 1
for (int j = 2 * i; j < n; j += i) {
isComposite[j] = true;
}
}
return count;
}
}
