一、題目描述
統(tǒng)計(jì)所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量湖笨。
示例:
輸入: 10
輸出: 4
解釋: 小于 10 的質(zhì)數(shù)一共有 4 個(gè), 它們是 2, 3, 5, 7 腕侄。
二、解題思路
用素?cái)?shù)篩算法：https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95
image
三例驹、代碼實(shí)現(xiàn)
class Solution {
public:
int countPrimes(int num) {
vector<bool> vec(num ,true);
int cnt = 0;
for (int i = 2; i < num; i++) {
if (vec[i]) cnt++;
for (int j = i+i; j < num; j+=i) {
vec[j] = false;
}
}
return cnt;
}
};
