埃拉托斯特尼筛法

简介

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种简单且古老的算法，用于找出一定范围内所有的素数。其核心思想是从最小的素数开始，逐步标记其倍数为合数，最终未被标记的数即为素数。

算法步骤

1. 创建一个布尔数组 is_prime[0..n]，初始全部设为 True。
2. 将 0 和 1 标记为 False，因为它们不是素数。
3. 从 i = 2 开始，若 i 是素数，则将其所有倍数（从 i*i 开始）标记为 False。
4. 优化：只需遍历到 sqrt(n)，因为大于 sqrt(n) 的倍数会被更小的素数覆盖。
5. 最后，收集所有仍为 True 的索引，即为素数。

时间复杂度

• 时间复杂度：O(n log log n)，非常接近线性。
• 空间复杂度：O(n)，用于存储布尔数组。

Python 实现

def sieve_of_eratosthenes(n):
    if n < 2:
        return []

    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    limit = int(n ** 0.5) + 1

    for i in range(2, limit):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    primes = [x for x in range(2, n + 1) if is_prime[x]]
    return primes

切片复制

def sieve_of_eratosthenes(n):
    if n < 2:
        return []

    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    limit = int(n ** 0.5) + 1
    for i in range(2, limit):
        if is_prime[i]:
            is_prime[i*i::i] = [False] * len(is_prime[i*i::i])
    prime = [x for x in range(2, n + 1) if is_prime[x]]
    return prime