编写程序,使用筛选法求解小于 n 的所有素数。
时间: 2023-06-12 11:07:10 浏览: 147
python使用筛选法计算小于给定数字的所有素数
以下是使用筛选法求解小于 n 的所有素数的 Python 代码:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
for j in range(i * i, n + 1, i):
primes[j] = False
return [i for i in range(2, n + 1) if primes[i]]
```
该函数使用布尔数组 primes 来表示每个数字是否为素数,首先将所有数字初始化为 True,然后从 2 开始遍历到 n 的平方根,如果当前数字 i 是素数,则将 i 的倍数标记为非素数。最后返回所有标记为素数的数字。
阅读全文