线性筛法python
时间: 2025-06-14 12:40:22 浏览: 12
### Python 线性筛法实现与解释
线性筛法(欧拉筛法)是一种高效的算法,用于筛选出小于等于给定数 \( n \) 的所有素数。相比埃氏筛法,线性筛法通过避免重复标记合数,将时间复杂度降低到 \( O(n) \)[^3]。
以下是 Python 实现的线性筛法代码示例:
```python
def linear_sieve(n):
# 初始化
is_prime = [True] * (n + 1) # 标记数组,True 表示当前数字可能是素数
primes = [] # 存储找到的素数
for i in range(2, n + 1):
if is_prime[i]: # 如果当前数字未被标记为非素数
primes.append(i) # 将其加入素数列表
# 使用已找到的素数标记当前数字的倍数为非素数
for p in primes:
if i * p > n: # 超过范围则停止
break
is_prime[i * p] = False # 标记为非素数
if i % p == 0: # 关键优化:当 i 是 p 的倍数时停止
break
return primes # 返回所有素数
# 示例:找出 50 以内的所有素数
primes = linear_sieve(50)
print("质数列表:", primes)
```
#### 代码解释
1. **初始化**:创建一个布尔数组 `is_prime`,长度为 \( n+1 \),初始值均为 `True`。数组索引表示数字,`True` 表示该数字可能是素数[^4]。
2. **遍历数字**:从 2 开始遍历到 \( n \)。如果当前数字 \( i \) 在 `is_prime` 中仍为 `True`,说明它是素数,将其加入 `primes` 列表[^3]。
3. **标记合数**:对于每个素数 \( p \),将 \( i \times p \) 标记为非素数。当 \( i \) 是 \( p \) 的倍数时,停止进一步标记,这是线性筛法的关键优化点。
4. **返回结果**:最终返回所有找到的素数列表。
#### 性能分析
- 时间复杂度:由于每个数字仅被其最小质因数标记一次,线性筛法的时间复杂度为 \( O(n) \)[^3]。
- 空间复杂度:需要一个大小为 \( n+1 \) 的布尔数组和一个存储素数的列表,空间复杂度为 \( O(n) \)[^4]。
#### 注意事项
在 Python 中,线性筛法的性能可能不如 C++ 等编译型语言高效[^2]。然而,Python 的简洁性和可读性使其非常适合教学和快速实现。
阅读全文
相关推荐

















