这个问题问得相当好,也很核心!埃氏筛法之所以只筛到根号 n,是因为它背后的数学原理,而且理解了这一点,你会发现这个算法的设计非常巧妙。
我们来一点点拆解它,就像剥洋葱一样,一层一层地看清楚。
什么是埃氏筛法?
首先,快速回顾一下埃氏筛法的基本操作:
1. 从 2 开始,将所有 2 的倍数标记为合数。
2. 找到下一个未被标记的数(也就是 3),将所有 3 的倍数标记为合数。
3. 重复这个过程:找到下一个未被标记的数(也就是 5),将所有它的倍数标记为合数,直到我们考虑完所有的数。
最后,那些没有被标记的数,就是质数。
核心问题:为什么只需要检查到 $sqrt{n}$?
这里的关键在于一个性质:任何一个合数 $N$,它一定有一个小于或等于它的平方根的质因数。
让我们来证明一下这个性质。
假设 $N$ 是一个合数,那么根据定义,它可以被分解成两个更小的正整数的乘积:
$N = a imes b$
这里,我们假设 $a$ 和 $b$ 都是大于 1 的整数。
现在考虑 $a$ 和 $b$ 的大小关系:
情况一:$a = b$
那么 $N = a imes a = a^2$。
此时,$a = sqrt{N}$。所以,$N$ 有一个因数 $a$,而 $a$ 等于 $sqrt{N}$。
情况二:$a
eq b$
不失一般性,我们假设 $a < b$。
如果 $a > sqrt{N}$,那么由于 $a < b$,我们自然就有 $b > sqrt{N}$。
那么 $a imes b > sqrt{N} imes sqrt{N} = N$。
但是我们知道 $a imes b$ 正好等于 $N$。这就产生了矛盾!
所以,为了避免这个矛盾,我们必须接受一个事实:在 $a imes b = N$ 的分解中,至少有一个因数(在 $a < b$ 的假设下就是 $a$)必须小于或等于 $sqrt{N}$。
埃氏筛法的逻辑与 $sqrt{n}$ 的关系
现在,我们把这个性质应用到埃氏筛法上。我们的目标是找出所有小于等于 $n$ 的质数。
埃氏筛法的过程是这样的:
我们用一个数字(我们称它为“筛子”)去筛掉它的倍数。
比如,我们用 2 去筛掉所有 2 的倍数(4, 6, 8, ...)。
然后用 3 去筛掉所有 3 的倍数(6, 9, 12, ...)。
然后用 5 去筛掉所有 5 的倍数(10, 15, 20, ...)。
当我们在筛掉一个合数 $N$ 的倍数时,我们实际上是在执行这个动作:
如果 $N$ 是合数,那么 $N$ 肯定已经被某个更小的质数 $p$ 筛过了(即 $N$ 是 $p$ 的倍数)。
当轮到用 $p$ 去筛掉它的倍数时,所有 $N$ 的倍数(例如 $k imes N$)也都会被筛掉。
而因为 $N$ 本身已经被筛过了,那么当轮到用 $N$ 这个合数去筛掉它的倍数时,这些倍数实际上早已经被 $p$ 或其他更小的质数筛过了。
我们只需要用质数去筛掉它们的倍数。 因为任何合数都一定能被它的最小质因数筛掉。
考虑一个合数 $N le n$。
根据上面证明的性质,我们知道 $N$ 一定有一个质因数 $p$ 满足 $p le sqrt{N}$。
由于 $N le n$,所以 $p le sqrt{N} le sqrt{n}$。
这意味着什么呢?
任何一个小于或等于 $n$ 的合数 $N$,在我们的埃氏筛过程中,它必然会在我们用某个小于或等于 $sqrt{n}$ 的质数 $p$ 来筛掉它的倍数时被标记为合数。
也就是说,我们只要确保我们已经用完了所有小于或等于 $sqrt{n}$ 的质数来筛除它们的倍数,那么所有小于等于 $n$ 的合数就已经都被标记过了。
举个例子,我们想找出 100 以内的质数。
我们需要筛到 $sqrt{100} = 10$。
我们需要用 2, 3, 5, 7 来筛。
用 2 筛掉:4, 6, 8, 10, ..., 100
用 3 筛掉:6, 9, 12, 15, ..., 99
用 5 筛掉:10, 15, 20, 25, ..., 100
用 7 筛掉:14, 21, 28, 35, 42, 49, ..., 98
现在,我们来看看那些还没有被筛掉的数字,比如 11。
11 是质数。
如果 11 是一个合数,那么它一定有一个小于等于 $sqrt{11}$ 的质因数。 $sqrt{11}$ 大约是 3.3。比 3.3 小的质数只有 2 和 3。
11 不是 2 的倍数。
11 不是 3 的倍数。
所以,11 不可能是合数,它必然是质数。
再看一个例子,比如 13。$sqrt{13}$ 大约是 3.6。比 3.6 小的质数是 2, 3。
13 不是 2 的倍数。
13 不是 3 的倍数。
所以 13 是质数。
再看 91。91 的平方根大约是 9.5。比 9.5 小的质数是 2, 3, 5, 7。
91 不是 2 的倍数。
91 不是 3 的倍数 (9+1=10,不能被 3 整除)。
91 不是 5 的倍数 (末尾不是 0 或 5)。
91 是 7 的倍数! $91 = 7 imes 13$。
你看,当轮到我们用 7 来筛掉它的倍数时,91 就会被标记为合数。而我们之所以能做到这一点,是因为 7 小于等于 $sqrt{91}$。
重点在于:
当埃氏筛进行到某个质数 $p$ 时,它会筛掉所有 $p$ 的倍数。
我们只需要进行到 $sqrt{n}$ 就可以了,因为:
1. 所有小于等于 $sqrt{n}$ 的质数,它们在筛过程中会正确地将它们的倍数标记为合数。
2. 所有大于 $sqrt{n}$ 的合数,它们自身肯定有一个小于等于 $sqrt{n}$ 的质因数。这个质因数在前面的步骤中就已经被用来标记这个合数了。
举个例子,假设我们要找 50 以内的质数,$sqrt{50} approx 7.07$。所以我们要用 2, 3, 5, 7 来筛。
2 会筛掉 4, 6, 8, ..., 50。
3 会筛掉 6, 9, 12, ..., 48。
5 会筛掉 10, 15, 20, ..., 50。
7 会筛掉 14, 21, 28, 35, 42, 49。
现在,考虑一个比 7 大但小于等于 50 的合数,比如 25。$25 = 5 imes 5$。5 小于 $sqrt{25}$,也小于 $sqrt{50}$。所以在用 5 筛的时候,25 就被标记了。
再比如 39。$39 = 3 imes 13$。3 小于 $sqrt{39}$,也小于 $sqrt{50}$。所以在用 3 筛的时候,39 已经被标记了。
再比如 49。$49 = 7 imes 7$。7 小于 $sqrt{49}$,也小于 $sqrt{50}$。所以在用 7 筛的时候,49 被标记了。
再比如 38。$38 = 2 imes 19$。2 小于 $sqrt{38}$,也小于 $sqrt{50}$。所以在用 2 筛的时候,38 已经被标记了。
最后,剩下的所有未被标记的数字,它们必然没有小于等于 $sqrt{n}$ 的质因数。
如果一个数 $x$ 没有小于等于 $sqrt{x}$ 的质因数,那么它就一定是质数。因为如果 $x$ 是合数,它必然能分解成 $a imes b$,而其中至少有一个因子(比方说 $a$)是小于等于 $sqrt{x}$ 的。
所以,当埃氏筛法执行完用所有小于等于 $sqrt{n}$ 的质数去筛除倍数的步骤后,所有小于等于 $n$ 的合数都已经因为存在一个小于等于 $sqrt{n}$ 的质因数而被标记了。剩下的未被标记的数,自然就是小于等于 $n$ 的质数。
总结一下:
任何一个合数 $N$ 都至少有一个小于或等于其平方根 $sqrt{N}$ 的质因数。
埃氏筛法是通过用质数去“筛”掉它们的倍数来工作的。
如果我们要找出所有小于等于 $n$ 的质数,我们只需要用所有小于等于 $sqrt{n}$ 的质数去执行这个筛除操作就足够了。
原因在于,任何一个小于等于 $n$ 的合数 $N$,它一定有一个小于等于 $sqrt{N}$ 的质因数 $p$。而 $sqrt{N} le sqrt{n}$。这意味着,这个质因数 $p$ 一定小于等于 $sqrt{n}$。所以在我们用所有小于等于 $sqrt{n}$ 的质数进行筛除时,这个合数 $N$ 必然会被它的这个“小”质因数 $p$ 筛掉。
因此,当筛到 $sqrt{n}$ 这一步为止时,所有小于等于 $n$ 的合数都已经无一例外地被标记出来了。剩下的未被标记的数,就是我们要找的质数。
这个设计非常简洁高效,因为它避免了不必要的计算。我们不必用比 $sqrt{n}$ 大的质数去筛除它们的倍数,因为这些倍数(如果它们本身小于等于 $n$ 的话)早就被它们更小的质因数筛掉了。