python欧拉筛法

Python欧拉筛法是一种用于高效地求解素数的算法。它基于一个重要的数论定理：任何一个合数都可以分解为若干个素数的乘积。欧拉筛法通过不断地筛选掉合数，最终得到一系列素数。

具体实现步骤如下：
1. 创建一个长度为n+1的布尔数组is_prime，初始化所有元素为True，表示所有数都是素数。
2. 将is_prime[0]和is_prime设置为False，因为0和1不是素数。
3. 从2开始遍历到n，如果is_prime[i]为True，则将i的所有倍数is_prime[j]（j=i*i, i*i+i, i*i+2i, ...）设置为False，因为它们都是合数。
4. 遍历完毕后，is_prime中为True的索引即为素数。

以下是Python欧拉筛法的实现代码：

def euler_sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(n**0.5) + 1):
        if is_prime[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

使用该算法可以快速得到小于等于n的所有素数。例如，调用`euler_sieve(20)`将返回[2, 3, 5, 7, 11, 13, 17, 19]。