python欧拉筛法求素数

欧拉筛法是求解素数的一种高效算法，它的基本思想是通过筛去合数来得到素数。下面是Python实现欧拉筛法求素数的示例代码：

def euler_sieve(n):
    primes = []
    is_prime = [True] * (n + 1)
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
        for j in range(len(primes)):
            if i * primes[j] > n:
                break
            is_prime[i * primes[j]] = False
            if i % primes[j] == 0:
                break
    return primes

在这个函数中，我们首先创建了一个布尔数组`is_prime`，并将其全部初始化为`True`，表示在开始时所有的数都是素数。然后，我们从2开始遍历到`n`，如果当前这个数是素数，我们就把它加入到`primes`数组中，并且把它的倍数全部标记为合数（即将`is_prime[i * primes[j]]`置为`False`）。

最后，我们返回`primes`数组中的所有素数即可。