埃式筛选法求素数python
时间: 2023-10-13 10:18:32 浏览: 94
以下是Python代码实现埃氏筛法求素数:
```python
def eratosthenes(n):
# 创建一个长度为n的数组,将所有元素初始化为True
is_prime = [True] * (n + 1)
# 0和1不是素数,将它们标记为False
is_prime[0] = is_prime[1] = False
# 从2开始遍历到n,标记素数的倍数为False
for i in range(2, n + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
# 返回所有素数的列表
return [i for i in range(2, n + 1) if is_prime[i]]
```
使用方法:
```python
primes = eratosthenes(100)
print(primes)
```
输出结果为:
```
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
```
该算法的时间复杂度为 O(nloglogn),是一种高效的求素数方法。
相关问题
筛选法求素数python
筛选法(Sieve of Eratosthenes)是一种用于求解素数的经典算法。它的基本思想是从2开始,将所有的倍数标记为合数,直到遍历完所有的数。剩下未被标记的数即为素数。
以下是使用Python实现筛选法求素数的代码示例:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的布尔数组,用于标记是否为素数
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False # 0和1不是素数
# 从2开始遍历到sqrt(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
# 示例:求解100以内的素数
primes = sieve_of_eratosthenes(100)
print(primes)
```
运行以上代码,将会输出100以内的所有素数。
使用列表实现筛选法求素数Python代码
下面是使用列表实现筛选法求素数的 Python 代码:
```python
def sieve_of_eratosthenes(n):
""" 使用筛选法求出小于等于n的素数 """
primes = [True] * (n + 1)
primes[0], primes[1] = False, False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
for j in range(i ** 2, n + 1, i):
primes[j] = False
return [i for i in range(n + 1) if primes[i]]
# 测试代码
print(sieve_of_eratosthenes(30))
```
此代码使用了一个名为 `primes` 的布尔列表,其中 `primes[i]` 表示 `i` 是否为素数。一开始将所有数都标记为素数,然后从2开始,将其倍数标记为非素数。最后,将所有标记为素数的数添加到一个列表中并返回。