问题描述
统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
提示：
解题思路
常规做法（超时）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution:
def countPrimes(self, n: int) -> int:
if n <= 1:
return 0
ans = 0
for i in range(2, n):
j = 2
flag = True
while j * j <= i:
if i % j == 0:
flag = False
break
j += 1
if flag:
ans += 1
return ans
|
埃拉托斯特尼筛法 (Sieve of Eratosthenes)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | # class Solution:
# def countPrimes(self, n: int) -> int:
# if n < 3:
# return 0
# f = [True] * n
# i = 2
# while i * i < n:
# if f[i]:
# j = i
# while i * j < n:
# f[i * j] = False
# j += 1
# i += 1
# return sum(f) - 2
class Solution:
def countPrimes(self, n: int) -> int:
if n < 3:
return 0
f = [True] * n
i = 2
while i * i < n:
if f[i]:
f[i * i : n : i] = [False] * len(range(i * i, n, i))
i += 1
return sum(f) - 2
|
线性筛法/欧拉筛法 (Euler's sieve)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution:
def countPrimes(self, n: int) -> int:
f = [True] * n
primes = []
for i in range(2, n):
if f[i]:
primes.append(i)
for prime in primes:
j = i * prime
if j >= n:
break
f[j] = False
if i % prime == 0:
break
return len(primes)
|