python使用筛选法求解小于n的所有素数
时间: 2023-04-27 07:00:25 浏览: 139
Python使用筛选法求解小于n的所有素数的方法如下:
1. 首先创建一个长度为n的布尔数组,初始化为True,表示所有数都是素数。
2. 从2开始遍历数组,如果当前数是素数,则将它的倍数标记为非素数,即将对应位置的布尔值设为False。
3. 遍历完数组后,所有布尔值为True的位置所对应的数就是小于n的所有素数。
下面是Python代码实现:
def sieve_of_eratosthenes(n):
is_prime = [True] * n
is_prime[] = is_prime[1] = False
for i in range(2, int(n ** .5) + 1):
if is_prime[i]:
for j in range(i * i, n, i):
is_prime[j] = False
return [i for i in range(n) if is_prime[i]]
# 示例
print(sieve_of_eratosthenes(20)) # 输出 [2, 3, 5, 7, 11, 13, 17, 19]
相关问题
编写python程序,使用筛选法求解小于n的所有素数
下面是一个使用筛选法求解小于n的所有素数的python程序:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的列表,用于记录每个数字是否为素数
is_prime = [True] * (n + 1)
# 0和1不是素数,将其标记为False
is_prime[0] = is_prime[1] = False
# 从2开始,遍历到n的平方根
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
# 如果i是素数,则将i的倍数标记为False
for j in range(i ** 2, n + 1, i):
is_prime[j] = False
# 返回小于n的所有素数
return [i for i in range(2, n + 1) if is_prime[i]]
# 测试程序
print(sieve_of_eratosthenes(30)) # 输出 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
```
在上面的程序中,我们使用了一个长度为n+1的列表is_prime来记录每个数字是否为素数。初始时,我们将所有数字都标记为素数(True),然后从2开始,遍历到n的平方根,如果当前数字i是素数,则将i的倍数标记为非素数(False),最后返回小于n的所有素数。
用python写出使用筛选法求解小于n的所有素数
好的,这个问题可以用Python语言中的筛选法,即埃氏筛法来解决。具体实现如下:
```python
def find_prime(n):
# 初始状态下,先将 0 和 1 标记为非质数
is_prime = [False, False] + [True] * (n-2)
prime_list = []
for i in range(2, n):
if is_prime[i]:
prime_list.append(i)
# 将当前质数的倍数标记为非质数
for j in range(i * i, n, i):
is_prime[j] = False
return prime_list
```
这个函数接收一个整数 n 作为参数,返回小于 n 的所有素数。函数首先将 0 和 1 标记为非质数,然后从 2 开始遍历到 n-1,对于每个质数,将其倍数标记为非质数,最后返回所有质数。