简单讲解：素数查找算法（基础方法+埃氏筛+欧拉筛）-之三：欧拉筛的实现

3.1 原理解释

欧拉筛（Euler’s sieve）是一种高效的质数筛选算法，通过遍历每个数并标记其最小质因数来筛选出所有素数。与埃氏筛不同，欧拉筛只标记每个数一次，因此其时间复杂度为 O(n)。

具体步骤如下：

创建一个长度为n+1的数组is_prime，初始化所有元素为True。is_prime[i]表示数字i是否为素数。

遍历2到n的每个数i，执行以下操作：

如果is_prime[i]为True，说明i为素数，将i加入素数列表primes。
遍历素数列表primes中的每个素数p，如果i * p <= n，将is_prime[i * p]置为False。
如果i能整除p，跳出内层循环，避免重复标记。
在欧拉筛中，我们利用了一个重要性质：每个合数都有一个最小质因数，而这个最小质因数不会大于它的平方根。因此，在遍历过程中，我们只需要标记每个数的最小质因数即可，无需遍历它的倍数。

3.2 算法实现

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 p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False
            if i % p == 0:
                break

    return primes

在代码中，我们首先创建了一个长度为n+1的数组is_prime，并初始化所有元素为True。然后，我们遍历2到n的每个数i，在遍历过程中利用已知的素数列表primes来标记每个数的最小质因数。如果is_prime[i]为True，说明i为素数，将其添加到primes列表中。

欧拉筛的时间复杂度为 O(n)，因为每个数只会被标记一次。这使得欧拉筛成为了一种高效的计算素数的算法。