首页python实现欧拉筛

python实现欧拉筛

时间: 2025-01-09 17:58:25 浏览: 81

### 使用 Python 实现欧拉筛法（线性筛）欧拉筛是一种高效的算法，能够在 O(n) 时间复杂度内找到给定范围内所有的素数。下面展示了一个完整的 Python 函数来实现这一方法。 ```python def euler_sieve(n): # 初始化标记数组，默认所有数都是素数（未标记） is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False primes = [] # 用于存储素数 for i in range(2, n + 1): if is_prime[i]: # i 是素数，将其加入素数列表 primes.append(i) # 标记 i 的倍数为合数 for j in range(i * i, n + 1, i): is_prime[j] = False return primes ``` 上述代码实现了基本的欧拉筛逻辑[^2]。然而，在实际应用中为了进一步优化性能并减少不必要的计算量，通常会对该算法稍作调整： ```python def optimized_euler_sieve(n): is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False 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: break return primes ``` 在这个版本里，当 `i` 能够整除某个已知质数 `p` 时就会停止继续尝试其他更大的质因数，因为此时再往后产生的任何新复合数都已经在之前的轮次中标记过了[^4]。通过这种方式不仅提高了效率还减少了重复劳动，使得整个过程更加简洁高效。

阅读全文