leetcode原题链接：204. 计数质数
很直观的思路是我们枚举每个数判断其是不是质数，枚举没有考虑到数与数的关联性，因此难以再继续优化时间复杂度。介绍一个常见的算法, 该算法由希腊数学家厄拉多塞（Eratosthenes ) 提出，称为厄拉多塞筛法，简称埃氏筛。
我们考虑这样一个事实：如果
x
x
x 是质数，那么大于
x
x
x 的
x
x
x 的倍数
2
x
,
3
x
,
…
2 x, 3 x, \ldots
2x,3x,… 一定不是质数，因此我们可以从 这里入手。
我们设
i
s
Prime
[
i
]
i s \operatorname{Prime}[i]
isPrime[i] 表示数
i
i
i 是不是质数，如果是质数则为
1
1
1，否则为
0
0
0。 从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即
0
0
0，这样在运行结束的时候我们即能知道质数的个数。
这里还可以继续优化, 对于一个质数
x
,
x,
x, 如果前面说的我们从
2
x
2 x
2x 开始标记其实是冗余的, 应该直接从
x
⋅
x
x \cdot x
x⋅x 开始标记
,
,
, 因为
2
x
,
3
x
,
…
2 x, 3 x, \ldots
2x,3x,… 这些数一定在
x
x
x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。
注意，0和1不是质数。
class Solution:
# 埃氏筛
def countPrimes(self, n: int) -> int:
if n <= 0: return 0
isPrime = [0]*2 + [1] *(n-2)
res = 0
for i in range(2, n, 1):
if isPrime[i]:
res += 1
if i*i < n:
for j in range(i*i, n, i):
isPrime[j] = 0
return res复杂度分析
时间复杂度：
O
(
n
log
n
)
O(n\log n)
O(nlogn)
空间复杂度：
O
(
n
)
O(n)
O(n)，需要
O
(
n
)
O(n)
O(n)的空间记录每个数是否为质数。
埃氏筛其实还是存在冗余的标记操作，比如对于 15 这个数，它会同时被 3，5 两个数标记为合数，因此我们优化的目标是让每个合数只被标记一次，这样时间复杂度即能保证为
O
(
n
)
O(n)
O(n)，这就是接下来要介绍的线性筛。
相较于埃氏筛，需要多维护一个
p
r
i
m
e
s
pr i m e s
primes 数组表示当前得到的质数集合。我们从小到大遍历，如果当前的数
x
x
x 是质数，就将其加入
p
r
i
m
e
s
primes
primes数组。
另一点与埃氏筛不同的是, 「标记过程」不再仅当
x
x
x 为质数时才进行，而是对每个整数
x
x
x 都进行。对于整数
x
x
x，我们不再标记其所有的倍数
x
⋅
x
,
x
⋅
(
x
+
1
)
,
…
,
x \cdot x, x \cdot(x+1), \ldots,
x⋅x,x⋅(x+1),…, 而是只标记质数集合中的数与
x
x
x 相乘的数，即
primes
0
∗
x
,
_{0} * x,
0∗x, primes
1
∗
x
,
…
,
_{1} * x, \ldots,
1∗x,…, 且在发现
x
x
x mod primes
i
=
0
_{i}=0
i=0 的时候结束当前标记。
核心点在于：如果
x
x
x 可以被 primes
i
i
i 整除，那么对于合数
y
=
x
⋅
y=x \cdot
y=x⋅ primes
i
+
1
i+1
i+1 而言，它一定在后面遍历到
x
p
r
i
m
e
s
i
⋅
p
r
i
m
e
s
i
+
1
\frac{x}{p r i m e s_{i}} \cdot p r i m e s_{i+1}
primesix⋅primesi+1 这个数的时候会被标记，其他同理，这保证了每个合数只会被其「最小的质因数」筛去，即每个合数被标记一次。
class Solution:
# 线性筛
def countPrimes(self, n: int) -> int:
if n <= 0: return 0
isPrime = [0]*2 + [1] *(n-2)
primes = []
for i in range(2, n, 1):
if isPrime[i]:
primes.append(i)
for _, prime in enumerate(primes):
if i*prime >= n:
break
isPrime[i*prime] = 0
if i % prime == 0:
break
return len(primes)复杂度分析
时间复杂度：
O
(
n
)
O(n)
O(n)，线性筛保证每个合数只被其最小质因子筛掉一次，所以理论上算法复杂度是
O
(
n
)
O(n)
O(n)线性时间复杂度。
空间复杂度：
O
(
n
)
O(n)
O(n)，需要
O
(
n
)
O(n)
O(n)的空间记录每个数是否为质数。