素数筛法
发布于2021-04-19
上次编辑2021-04-19
普通方法
1
2
3
4
5
6
7
8
9
10
11
12
13 | def primes_under_n(n: int) -> List[int]:
primes = []
for i in range(2, n + 1):
j = 2
is_prime = True
while j * j <= i:
if i % j == 0:
is_prime = False
break
j += 1
if is_prime:
primes.append(i)
return primes
|
埃拉托斯特尼筛法
Sieve of Eratosthenes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | def eratosthenes_sieve(n: int) -> List[int]:
is_prime = [True] * (n + 1)
i = 2
while i * i <= n:
if is_prime[i]:
j = i
while j * i <= n:
is_prime[j * i] = False
j += 1
i += 1
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
return primes
|
线性筛法
欧拉筛法 (Euler's sieve).
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | def euler_sieve(n: int) -> List[int]:
is_prime = [True] * (n + 1)
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for prime in primes:
x = i * prime
if x > n:
break
is_prime[x] = False
if i % prime == 0:
break
return primes
|
使用 Python 时，最快的是用下面代码写的 埃拉托斯特尼筛法。
1
2
3
4
5
6
7
8
9
10
11
12 | def eratosthenes_sieve(n: int) -> List[int]:
is_prime = [True] * (n + 1)
i = 2
while i * i <= n:
if is_prime[i]:
is_prime[i * i : n + 1 : i] = [False] * len(range(i * i, n + 1, i))
i += 1
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
return primes
|
例题