欧拉筛法python
时间: 2024-03-29 16:33:20 浏览: 303
线性素筛 欧拉函数 区间筛素数.zip_sowoc_算法 欧拉函数 线性筛
欧拉筛法(Sieve of Eratosthenes)是一种用于找出一定范围内所有素数的算法。它的基本思想是从小到大遍历每个数,将其所有的倍数标记为合数,最终剩下的未被标记的数即为素数。
以下是使用Python实现欧拉筛法的代码示例:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的布尔数组,用于标记数字是否为素数
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = 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)
```
这段代码将输出从2到100之间的所有素数。
阅读全文