筛法(挨拉托色尼筛法)是一种用来求所有小于N的素数的方法。用筛法求素数的基本思想# 是:把从2到n的一组正整数从小到大按顺序排列。从中依次删除2的倍数、3的倍数、5的倍# 数,直到根号N的倍数为止,剩余的即为2~N之间的所有素数。用python语言用筛法求素数
时间: 2024-02-13 07:59:44 浏览: 156
以下是用 Python 实现筛法求素数的代码:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为 n+1 的布尔数组,用于标记每个数是否为素数,默认都为 True
is_prime = [True] * (n+1)
# 0 和 1 都不是素数,因此将其标记为 False
is_prime[0] = is_prime[1] = False
# 从 2 开始遍历数组,如果当前数字是素数,则将其倍数全部标记为 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
# 将所有标记为 True 的数字添加到结果列表中
primes = []
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
return primes
```
你可以调用 `sieve_of_eratosthenes(n)` 函数来得到小于等于 `n` 的所有素数。例如,如果要得到小于等于 100 的所有素数,可以这样调用:
```python
primes = sieve_of_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]
```
阅读全文