埃氏筛法python
时间: 2024-04-12 16:25:03 浏览: 18
埃氏筛法(Sieve of Eratosthenes)是一种用于找出一定范围内所有素数的算法。它的基本思想是从2开始,将每个素数的倍数标记为合数,直到遍历完所有小于给定范围的数。以下是埃氏筛法的Python实现:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的布尔数组,用于标记数字是否为素数
is_prime = [True] * (n + 1)
is_prime = is_prime = False # 0和1不是素数
# 从2开始遍历到根号n
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
# 将i的倍数标记为合数
for j in range(i * i, n + 1, i):
is_prime[j] = False
# 收集所有素数
primes = [i for i in range(n + 1) if is_prime[i]]
return primes
```
使用示例:
```python
n = 100
primes = sieve_of_eratosthenes(n)
print(primes)
```
这段代码将输出小于等于100的所有素数。
相关问题
埃氏筛法与欧拉筛python
埃氏筛法:
```python
def Eratosthenes(n):
primes = [True] * (n + 1)
primes[0], primes[1] = False, False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n + 1: i] = [False] * len(primes[i * i: n + 1: i])
return [i for i in range(n + 1) if primes[i]]
```
欧拉筛:
```python
def Euler(n):
primes = []
is_prime = [True] * (n + 1)
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
for p in primes:
if i * p > n:
break
is_prime[i * p] = False
if i % p == 0:
break
return primes
```
两者的时间复杂度都是 $O(n \log \log n)$,但在常数上欧拉筛比埃氏筛法小,因此欧拉筛法更快。
python实现埃氏筛法求2~10000素数
埃氏筛法是一种用于求解一定范围内素数的算法。下面是使用Python实现埃氏筛法求解2~10000的素数的代码:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的列表,用于标记数字是否为素数,初始全部为True
primes = [True] * (n + 1)
# 将0和1标记为非素数
primes[0] = primes[1] = False
p = 2
while p * p <= n:
# 如果p没有被标记为非素数,则p一定是素数,因此将p及其倍数标记为非素数
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
# 返回所有标记为素数的数字
return [i for i in range(n + 1) if primes[i]]
# 调用函数并打印结果
primes = sieve_of_eratosthenes(10000)
print(primes)
```
以上代码实现了一个名为`sieve_of_eratosthenes`的函数,该函数接受一个参数`n`,用于指定范围。函数内部使用了一个长度为`n+1`的列表`primes`来标记数字是否为素数,其中初始全部为`True`。然后从2开始,找到一个素数后,将其倍数都标记为非素数。最终,返回所有标记为素数的数字。
在主程序中,调用`sieve_of_eratosthenes`函数并传入10000作为参数,得到2~10000范围内的素数列表,并将其打印输出。