题解 AT5249 [ABC149C] Next Prime

· · 题解

介绍一种比较新颖的方法。

首先，我们先定义一个数组：a，用来存储 10^5 以下的质数。

判断质数的方法有很多，由于本题的数据范围较小，可以直接使用 \mathcal{O}(\sqrt{n}) 的试除法。

试除法原理：

对于一个数，一定有至少两个因数（1 和它本身）。

我们可以尝试去找到除这两个因数以外的因数。举个例子：

28\bmod1,\color{red}{2,4,7,14}\color{black}{,28=0}

这个例子中，标红的因数为「除这两个因数以外的因数」。

根据一个质数必定只有两个因数：1 和它本身。（1 除外）

所以，我们才会找其他的因数，如果找到了，证明这个数不是质数；如果没有找到，这个数就是质数。

可得代码：

bool prime(int a)
{
    for(int i = 2; i <= n; i++) if(a % i == 0) return 0;
    return 1;
}

但是，这个代码的时间复杂度是 \mathcal{O}(n)，还有提升的空间，可通过简单的方法进行优化。

观察刚刚 28 的因数：

28\bmod\color{red}{1},\color{blue}{2},\color{green}{4},7,\color{blue}{14},\color{red}{28}\color{black}{=0}

颜色相同的因数为「一对」，这两个数相乘等于 28，可得：

整数的因数成对出现（完全平方数除外）。

还可以试着用其他的数进行证明，这里不再赘述。

为什么完全平方数除外呢？举个例子：

25\bmod\color{red}{1},\color{blue}{5},\color{red}{25}

此处，1 和 25 成为「一对」，5 却剩下了。由于 5^2=25，这是不可避免的。

所以，还有一个定理：完全平方数的因数有奇数个。

由于因数是成对出现的，所以只要一个数能被「一半的」因数整除，必然能被「另一半的」因数整除（完全平方数除外）。

根据这个定理，可以直接枚举到 \sqrt{n}，时间复杂度自然就是 \mathcal{O}(\sqrt{n})。

写成代码：

bool prime(int a)
{
    for(int i = 2; i * i <= n; i++) if(a % i == 0) return 0;
    return 1;
}

不推荐在此处使用 sqrt 函数，以免发生奇奇怪怪的错误。

再回到开头的方法，把 a 数组求出来，范围是 2 到 10^5 的质数。可用循环轻松解决。

可写出代码（轻微压行）：

const int N = 1e5 + 5;
int a[N], cnt;
for(int i = 1; i <= N; i++) if(prime(i)) a[++cnt] = i;

由于我的下标习惯从 1 开始用，所以先进行累加，写成了 ++cnt 而不是 cnt++。使用后者会先存储，在更新 cnt，适合从 0 开使用下标。

接下来，输入 n 以后，直接查表即可。

代码：

for(int i = 1; i <= cnt; i++)
{
    if(a[i] >= n)
    {
        cout << a[i] << endl;
        break;
    }
}

把上述几个代码块拼接起来就是 AC 程序了，时间复杂度 \mathcal{O}(1)（由于需要枚举 N 个数是否为质数，所以复杂度为常量）。读者还可以了解更多的质数筛法，如线性筛、埃氏筛、欧拉筛等高效率的筛法。