自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:17:32，当前版本为作者最后更新于2025-06-17 11:41:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

本题考察质数、质因数分解。

我们从小往大枚举 $p_1$，逐一判断 $n$ 是否能够被 $p_1$ 整除。一般来说这是很快的，除非 $n$ 是一个质数。这个时候，$p_1$ 就不得不枚举到 $n$ 那么多。

我们应当怎么办呢？实际上，我们的 $p_1$ 只要枚举到 $\sqrt{n}$。这是为什么呢？$n$ 必然可以被表示为 $n=a\times b$（其中 $a<b$），例如说 $36=1\times 36=2\times 18=3\times 9=6\times 6$，这个情况下 $a$ 和 $b$ 恰巧在 $\sqrt{36}=6$ 的位置相等。如果要给 $n$ 做分解，在 $\leq \sqrt{n}$ 的位置没有找到 $a$，那么也必然找不到 $b$ 了。

我们还能再加加速，枚举的过程中，先把偶数判掉，这样我们只用判断奇数（例如 $3,5,7,\dots$ 这样枚举判断）。这样可以更进一步提升判断速度。

参考代码：

cin >> n;
// 如果 n 能被 2 整除，则 2 为最小质因子
if(n % 2 == 0){
    cout << 2 << "\n";
    continue;
}
// 从 3 开始遍历奇数
bool found = false;
for(long long i = 3; i * i <= n; i += 2){
    if(n % i == 0){
        cout << i << "\n";
        found = true;
        break;
    }
}
// 如果没有找到任何因子，则 n 为质数，其最小质因子为 n 本身
if(!found)
    cout << n << "\n";