如何在O(n)时间复杂度内计算出n以内的所有素数？

嘿，这个问题问到点子上了！咱们平时用的埃氏筛之所以达不到线性时间，就是因为很多合数会被多个素数重复标记（比如12会被2和3都标记一遍），白白浪费了时间。而**欧拉筛（也叫线性筛）**就是专门解决这个问题的，能做到严格的O(n)时间复杂度。

核心思路 #

欧拉筛的关键在于保证每个合数只被它的最小质因数标记一次，这样就彻底避免了重复操作。具体逻辑是：

• 维护一个已经找到的素数列表
• 遍历从2到n的每个数i：
  1. 如果i是素数，就把它加入素数列表
  2. 用当前数i去乘素数列表里的每个素数p，标记i*p为合数
  3. 当i能被p整除时，立刻停止继续乘后面的素数——因为此时i是p的倍数，i = k*p，后面的素数p' > p，那么i*p' = k*p*p'，这个数会在k*p'遍历到的时候被p标记（p是它的最小质因数），现在提前标记就会重复，所以必须停下来。

代码示例（Python） #

def linear_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:
            product = i * p
            if product > n:
                break  # 超过n就没必要继续了
            is_prime[product] = False
            # 核心优化：i能被p整除时停止，避免重复标记
            if i % p == 0:
                break
    return primes

为什么这是O(n)？ #

因为每个合数只会被它的最小质因数标记一次，整个过程中标记操作的总次数等于n以内合数的数量，加上筛选素数的遍历次数，整体就是线性的O(n)时间。比如12，它的最小质因数是2，只会在i=6、p=2的时候被标记一次，不会再被p=3重复标记；再比如18，最小质因数是2，只会在i=9、p=2的时候被标记一次。

这样一来，就完美解决了埃氏筛重复标记的问题，实现了线性时间复杂度的素数筛选。

内容的提问来源于stack exchange，提问作者Complexity