素数重学笔记

之前都没有怎么理解，现在来复习一下。

试除法

从 \(2\) 枚举到 \(\lfloor\sqrt n\rfloor\) 判断能否整除。

朴素筛法

从小到大枚举每个数，将范围内它的倍数全部标记为合数。

显然就是调和级数，时间复杂度 \(O(n\log n)\)。

埃氏筛

观察到一个合数必定可以通过某个质数乘上一个数得到。

从小到大枚举每个质数，将范围内它的倍数全部标记为合数。

当然有一个小优化，对于 \(i\) 这个质数，枚举 \(j\) 筛掉 \(i\times j\) 的时候我们强制钦定 \(i\leq j\)，如果 \(i>j\) 的话 \(i\times j\) 肯定在 \(j\) 中至少一个质因子那里筛过了。

时间复杂度 \(O(n\log\log n)\)，证明不在探讨的范围内。

欧拉筛

发现埃氏筛中的小优化没有优化彻底，一个合数仍然可能被筛多次。我们希望一个合数只在它最小的质因数那里被筛一次。

对于每个数 \(i\)，尝试枚举小于等于 \(i\) 的每个质数 \(p\) 同时筛去 \(p\times i\)。一旦 \(p|i\) 就直接退出循环。

为什么这样是对的呢？我们发现如果 \(p\times i\) 被一个比 \(p\) 更小的质数 \(q\) 筛去了，那么 \(q|i\)。

而之前肯定已经枚举过了 \(q\)，并跳出了循环，不可能做到 \(p\)。

于是这个东西就是线性的啦。