B4170 [BCSP-X 2024 6 月小学高年级组] 最小质因子

chen_zhe · 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";