class Solution {
public:
int countPrimes(int n) {
}
};
204. 计数质数
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：0
提示：
0 <= n <= 5 * 106原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 4.9 MB, 提交时间: 2020-11-23 14:39:37
func countPrimes(n int) int {
sign := make([]bool, n)
count := 0
for i:=2;i<n;i++ {
if sign[i] {
continue
}
count++
for j := 0; j<n;j+=i {
sign[j] = true
}
}
return count
}
python3 解法, 执行用时: 156 ms, 内存消耗: 36.2 MB, 提交时间: 2020-11-23 14:30:32
class Solution:
def countPrimes(self, n: int) -> int:
if n < 3:
return 0
output = [1] * n
output[0], output[1] = 0, 0
for i in range(2, int(n**0.5 + 1)):
if output[i] == 1:
output[i*i:n:i] = [0] * len(output[i*i:n:i])
return sum(output)