埃氏筛和欧拉筛python
时间: 2023-10-12 13:09:20 浏览: 51
埃氏筛和欧拉筛都是用来求质数的算法,下面分别介绍它们的python实现。
埃氏筛:
```python
def eratosthenes_sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
return primes
```
欧拉筛:
```python
def euler_sieve(n):
is_prime = [True] * (n + 1)
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for j in range(len(primes)):
if i * primes[j] > n:
break
is_prime[i * primes[j]] = False
if i % primes[j] == 0:
break
return primes
```
两者的区别在于,埃氏筛每次找到一个质数后,将它的倍数都标记为合数。而欧拉筛则是在每个质数的倍数中,只标记一次,避免了重复标记,从而提高了效率。