欧拉筛 python

欧拉筛是一种高效的素数筛法，可以在 $O(n)$ 的时间复杂度内求出 $n$ 以内的所有素数。下面是一个使用欧拉筛实现的 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 range(len(primes)):
            if i * primes[j] > n:
                break
            is_prime[i * primes[j]] = False
            if i % primes[j] == 0:
                break
    return primes

这个函数接受一个整数 $n$ 作为参数，返回一个列表，其中包含 $2$ 到 $n$ 之间的所有素数。函数首先创建一个布尔类型的数组 `is_prime`，用于记录每个数是否为素数。然后，它创建一个空列表 `primes`，用于存储已知的素数。接下来，函数从 $2$ 到 $n$ 遍历每个数 $i$，如果 $i$ 是素数，则将其添加到 `primes` 列表中，并将 $i$ 的倍数标记为非素数。在标记 $i$ 的倍数时，函数使用了一个小技巧，即如果 $i$ 能够整除某个已知素数 $p$，则不需要再标记 $i \times p$，因为 $i \times p$ 已经在遍历 $p$ 时被标记过了。这个技巧可以让算法的时间复杂度降为 $O(n)$。