素数重学笔记

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

试除法

从 (2) 枚举到 (lfloorsqrt n floor) 判断能否整除。

朴素筛法

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

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

埃氏筛

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

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

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

时间复杂度 (Oleft(nloglog n ight))，证明不在探讨的范围内。

欧拉筛

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

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

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

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

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