线性筛素数的Python实现

转载线性筛法 - _NachoNeko - 博客园 (cnblogs.com)

用于筛选素数

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
def sieve_of_eratosthenes(n):
"""
返回小于等于 n 的所有素数
"""
is_prime = [True] * (n + 1)
is_prime[1] = False
primes = set() # 存储素数的集合(列表之类都行)

for i in range(2, n + 1):
if is_prime[i]:
# i 是素数,将其添加到素数列表中
primes.add(i)
# 用素数 i 来筛去它的倍数
for prime in primes:
# 如果素数 prime 的平方大于 i,则跳出循环
# 因为 prime * prime > i 的倍数已经被更小的素数筛过了
if i * prime > n:
break
# 将 i 的 prime 倍数标记为非素数
is_prime[prime * i] = False
if i % prime == 0:
# 如果 i 是 prime 的倍数,跳出循环,针对该点下面会进行说明
break

return primes

说明

为什么当 i % prime == 0 时 break 可以避免重复计算,
下面证明会被下一个质数筛掉的合数,这个质数也能筛掉:

设prime的下一个质数设为 next_prime, i = d * prime
下一个将被筛掉的数为 next_prime * i = next_prime * d * prime
该合数会在 i = next_prime * d 时被 prime 筛掉