在编程竞赛和算法学习中，筛选质数是一项基本且常见的任务。其中，欧拉筛（也称为线性筛）以其高效性而著称。它的时间复杂度为O(n)，能够快速地找出指定范围内的所有质数。🌈

一、什么是欧拉筛？

欧拉筛的核心思想是每个合数只会被它的最小质因数筛掉一次。这意味着算法的执行效率非常高，可以保证每个数只处理一次。🚀

二、核心原理详解

- 初始化：创建一个布尔数组标记所有数为未访问状态。

- 遍历与标记：从2开始遍历，如果当前数字未被标记，则将其视为质数，并将该质数的倍数全部标记为非质数。

- 优化操作：在标记时，通过当前质数的倍数来实现，这样能确保每个合数仅被其最小质因数筛除。

三、代码实现

```python

def euler_sieve(n):

is_prime = [True] (n + 1)

primes = []

for i in range(2, n + 1):

if is_prime[i]:

primes.append(i)

for j in primes:

if i j > n:

break

is_prime[i j] = False

if i % j == 0:

break

return primes

```

通过上述步骤，我们可以高效地找到指定范围内的所有质数。掌握欧拉筛的核心原理，不仅有助于解决质数相关问题，还能加深对算法设计的理解。💡

希望这篇内容能帮助你更好地理解和应用欧拉筛法！👍