欧拉筛筛素数

学委

2018-07-03 12:35:51

Solution

*2020-02-01 更新* 想要快速地筛出一定上限内的素数? 下面这种方法可以保证范围内的每个合数都被删掉(在 bool 数组里面标记为非素数),而且任一合数只被: **“最小质因数 × 最大因数(非自己) = 这个合数”** 的途径删掉。由于每个数只被筛一次,时间复杂度为 $O(n)$。 # 欧拉筛 先浏览如何实现再讲其中的原理。 ___ ## 实现 ```cpp #include <cstdio> #include <cstring> bool isPrime[100000010]; //isPrime[i] == 1表示:i是素数 int Prime[6000010], cnt = 0; //Prime存质数 void GetPrime(int n)//筛到n { memset(isPrime, 1, sizeof(isPrime)); //以“每个数都是素数”为初始状态,逐个删去 isPrime[1] = 0;//1不是素数 for(int i = 2; i <= n; i++) { if(isPrime[i])//没筛掉 Prime[++cnt] = i; //i成为下一个素数 for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) { //从Prime[1],即最小质数2开始,逐个枚举已知的质数,并期望Prime[j]是(i*Prime[j])的最小质因数 //当然,i肯定比Prime[j]大,因为Prime[j]是在i之前得出的 isPrime[i*Prime[j]] = 0; if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子 break; //重要步骤。见原理 } } } int main() { int n, q; scanf("%d %d", &n, &q); GetPrime(n); while (q--) { int k; scanf("%d", &k); printf("%d\n", Prime[k]); } return 0; } ``` ___ ## 原理概述 代码中,外层枚举 $i = 1 \to n$。对于一个 $i$,经过前面的腥风血雨,如果它还没有被筛掉,就加到质数数组 $Prime[]$ 中。下一步,是用 $i$ 来筛掉一波数。 内层从小到大枚举 $Prime[j]$。$i×Prime[j]$ 是尝试筛掉的某个合数,其中,**我们期望 $Prime[j]$ 是这个合数的最小质因数 (这是线性复杂度的条件,下面叫做“筛条件”)**。它是怎么得到保证的? **$j$ 的循环中,有一句就做到了这一点:** ```cpp if(i % Prime[j] == 0) break; ``` $j$ 循环到 $i \mod Prime[j] == 0$ 就**恰好需要停止**的理由是: * 下面用 $s(smaller)$ 表示小于 $j$ 的数,$L(larger)$ 表示大于 $j$ 的数。 * **① $i$ 的最小质因数肯定是 $Prime[j]$。** (如果 $i$ 的最小质因数是 $Prime[s]$ ,那么 $Prime[s]$ 更早被枚举到(因为我们从小到大枚举质数),当时就要break) 既然 $i$ 的最小质因数是 $Prime[j]$,那么 $i × Prime[j]$ 的最小质因数也是 $Prime[j]$。所以,$j$ 本身是符合“筛条件”的。 * **② $i × Prime[s]$ 的最小质因数确实是 $Prime[s]$。** (如果是它的最小质因数是更小的质数 $Prime[t]$,那么当然 $Prime[t]$ 更早被枚举到,当时就要break) 这说明 $j$ 之前(用 $i × Prime[s]$ 的方式去筛合数,使用的是最小质因数)都符合“筛条件”。 * **③ $i × Prime[L]$ 的最小质因数一定是 $Prime[j]$。** (因为 $i$ 的最小质因数是 $Prime[j]$,所以 $i × Prime[L]$ 也含有 $Prime[j]$ 这个因数(这是 $i$ 的功劳),所以其最小质因数也是 $Prime[j]$(新的质因数 $Prime[L]$ 太大了)) 这说明,如果 $j$ 继续递增(将以 $i × Prime[L]$ 的方式去筛合数,没有使用最小质因数),是不符合“筛条件”的。 *小提示:* *当 $i$ 还不大的时候,可能会一层内就筛去大量合数,看上去耗时比较大,但是由于保证了筛去的合数日后将不会再被筛(总共只筛一次),复杂度是线性的。到 $i$ 接近 $n$ 时,每层几乎都不用做什么事。* 建议看下面两个并不复杂的证明,你能更加信任这个筛法,利于以后的扩展学习。 ## 正确性(所有合数都会被标记)证明 设一合数 $C$(要筛掉)的最小质因数是 $p_1$,令 $B = C / p_1$($C = B × p_1$),则 $B$ 的最小质因数不小于 $p_1$(否则 $C$ 也有这个更小因子)。那么当外层枚举到 $i = B$ 时,我们将会**从小到大**枚举各个质数;因为 $i = B$ 的最小质因数不小于 $p_1$,所以 $i$ 在质数枚举至 $p_1$ 之前一定不会break,**这回**,$C$ 一定会被 $B × p_i$ 删去。 **核心:亲爱的 $B$ 的最小质因数必不小于 $p_1$。** 例:$315 = 3 × 3 × 5 × 7$,其最小质因数是 $3$。考虑 $i = 315 / 3 = 105$ 时,我们从小到大逐个枚举质数,**正是因为** $i$ 的最小质因数**也**不会小于 $3$(本例中就是 $3$),所以当枚举 $j = 1 (Prime[j] = 2)$ 时,$i$ 不包含 $2$ 这个因子,也就**不会break**,直到 $Prime[j] = 3$ **之后**才退出。 *当然质数不能表示成“**大于1的某数×质数**”,所以整个流程中不会标记。* ## 线性复杂度证明 注意这个算法一直使用“某数×质数”去筛合数,又已经证明一个合数一定会被它的最小质因数 $p_1$ 筛掉,所以我们**唯一要担心的就是同一个合数是否会被“另外某数 × $p_1$ 以外的质数”再筛一次导致浪费时间**。设要筛的合数是 $C$,设这么一个作孽的质数为 $p_x$,再令 $A = C / p_x$,**则 $A$ 中一定有 $p_1$ 这个因子**。当外层枚举到 $i = A$,它想要再筛一次 $C$,却在枚举 $Prime[j] = p_1$ 时,因为 $i \mod Prime[j] == 0$ 就退出了。因而 $C$ 除了 $p_1$ 以外的质因数都不能筛它。 **核心:罪恶的 $A$ 中必有 $p_1$ 这个因子。** 例:$315 = 3 × 3 × 5 × 7$。首先,虽然看上去有两个 $3$,但我们筛数的唯一一句话就是 ```cpp isPrime[i*Prime[j]] = 0; ``` 所以,$315$ 只可能用 $105 × 3$ 或 $63 × 5$ 或 $45 × 7$ 这三次筛**而非四次**。然后,非常抱歉,后两个 $i = 63, i = 45$ 都因为贪婪地**要求对应的质数** $Prime[j]$ 为 $5$ 、$7$,而**自己被迫拥有** $3$ 这个因数,因此他们内部根本枚举不到 $5$ 、$7$,而是枚举到 $3$ 就break了。 以上两个一证,也就无可多说了。 ___ 更新日志: 2019-02-22 原理简化;用词修改或订正。 2019-04-02 一些用词更准确;加入更多括号内的注释,减少回看上文的需要。 2020-02-01 题面修改了,补充一下答案输出。