质数筛小记

本篇博客详细解析 LeetCode 204（Count Primes）的三种解法，包括枚举法、埃氏筛和欧拉筛（线性筛），并分析其时间复杂度与空间复杂度。

发表于 2024/12/11

次浏览 8 分钟阅读

作者 NOSAE

质数筛小记

前言

题目出自leetcode 204，本质上是为了筛选出小于n的所有质数。三种方法：

暴力枚举
埃氏筛
欧拉筛（线性筛）

枚举法

枚举法中我们只需要从 2 到 n 判断每个数是否质数即可。对于第 i 个数来说判断是否质数，只需要看其能否被 2 到 i-1 整除，如果有可以整除的则为合数，不能整除则为质数。

进一步优化，考虑到如果 y 是 x 的因数，那么 x/y 也必然是 x 的因数，因此我们只要校验 y 或者 x/y 即可。而如果我们每次选择校验两者中的较小数，则不难发现较小数一定落在 [2, sqrt(x)] 的区间中，因此我们只需要枚举 [2, sqrt(x)] 中的所有数即可。

时间复杂度：O(n*sqrt(n))

空间复杂度：O(1)

埃氏筛 Sieve of Eratosthenes

考虑质数 x，那么 x 的倍数一定是合数，因此可以将 2x、3x….这些 x 的倍数都标记为合数，如此一来，之后遇到这些数的时候就直接知道他们是合数，直接跳过即可。

进一步优化，不用从 2x 开始标记，而是从 x*x 开始标记，因为 2x 之前已经被 2 标记过，3x 已经被 3 标记过…

时间复杂度：O(n * logn * logn)

空间复杂度：O(n)

欧拉筛（线性筛）

在埃氏筛当中，许多合数会被重复标记，比如 6 会被 2 和 3 标记，15 会被 3 和 5 标记。由于一个合数很可能会被分解成多个不相同的质数的乘积，如 42 = 2 * 3 * 7，那么 42 就会被标记三次，造成时间复杂度上的浪费。

在欧拉筛的优化中，观察到每个合数被分解为质数乘积后，就拿 42 = 2 * 3 * 7 举例，必然存在一个最小的质数因子，这里是 2，比如 15 = 3 * 5 中的最小质数因子是3，因此欧拉筛的核心在于，让每个合数只被最小的质数因子标记，这样一来就能避免被其它质数因子重复标记。

那么如何做到每个合数只被最小的质数因子标记呢？首先我们维护一个按从小到大顺序的质数数组 primes。然后写出伪代码：

isPrime = bool[n] // 大小为n，全部初始化为true
primes = int[0] // 大小为0
for i in 2..n:
	if isPrime[i]:
		primes.push_back(i)
	for p in primes:
		isPrime[i*p] = false
		if (i%p == 0) break

首先对于任意一个数 i，可以表示成最小质因子 pi 乘上另一个数 num，即 i = pi * num，如 42 = 2 * 21，我们用 i 的倍数来标记后面的合数，这里的倍数因子从最小的质数开始遍历取得，当 i 被倍数因子整除，就停止使用 i 更大的倍数标记。

这里的核心在于，由于 i 的最小质因子是 pi，当 p 不能整除 i 时，说明 p < pi（因为 p 是从最小的质数开始获得的），那么对于 j = i * p，我们有 j 的最小质因子肯定是 p，因此我们做到了 j 被最小质因子标记。当遍历到的 p 第一次能整除 i 的时候，说明 p == pi，倘若不终止循环，下一个遍历到的 p 会大于 pi，对于此时的 j = i * p 中的p 就不再是 j 的最小质因子，此时 j 被最小质因子标记了一次，又被 p 标记了一次，导致重复标记。因此当 p 能整除 i 的时候终止遍历，就做到了 j 不会被非最小质因子标记。

时间复杂度：O(n)

空间复杂度：O(n)