跳到主要内容

AcWing 866. 试除法判定质数

本节目标

用安全的整除边界判断一个整数是否为质数。

这是质数判定与筛法的起点：当输入只有少量整数时，不需要建立整张质数表，而是直接寻找能否整除当前数的因子。

查看 AcWing 原题

题意与约束​

依次读入多个整数，对每个整数输出 Yes 或 No，表示它是否为质数。1 与所有小于 2 的整数都不是质数；完全平方数例如 49 也必须判为合数。

第一反应与瓶颈​

最直接的做法是枚举 2..n-1 的所有候选因子。这一定正确，但当 n 接近题目上界时，需要接近 n 次取模，远超过判断一个数真正需要的信息。

数学关系与算法推导​

若 n = a × b 且两个因子都大于 √n，乘积会大于 n，矛盾。因此合数一定有一个因子不大于平方根。只要从 2 枚举到这一边界，发现整除就返回 false；没有发现则为质数。

循环写成 divisor <= n / divisor，而不是 divisor <= sqrt(n)：前者仍等价于 divisor² <= n，却避开了浮点 sqrt 在完全平方数附近的舍入边界，也避免整数平方溢出。

正确性依据​

当算法找到整除的 divisor 时，n 有非平凡因子，故不是质数。反之，若算法结束仍未找到因子，所有不大于 √n 的整数都不能整除 n；任何合数都应在这一范围内至少有一个因子，因此 n 只能是质数。n < 2 单独返回 false 覆盖定义边界。

样例执行过程​

判断 97 时依次检查 2..9，没有因子，返回 Yes。判断 49 时，7 <= 49 / 7 且 49 % 7 == 0，立刻返回 No；不必继续尝试更大的数。

代码实现​

C++17
#include <iostream>

using namespace std;

bool isPrime(int n) {
    if (n < 2) {
        return false;
    }

    for (int divisor = 2; divisor <= n / divisor; divisor++) {
        if (n % divisor == 0) {
            return false;
        }
    }
    return true;
}

#ifndef ALGORITHM_TUTORIAL_TEST
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int count;
    cin >> count;
    while (count--) {
        int n;
        cin >> n;
        cout << (isPrime(n) ? "Yes" : "No") << '\n';
    }
}
#endif

核心函数 isPrime／is_prime 只接收一个整数并返回布尔值；入口逐项读取，再把布尔值格式化为题目要求的 Yes 或 No。

复杂度分析​

最多尝试 ⌊√n⌋ - 1 个候选因子，时间复杂度为 O(√n)，额外空间为 O(1)。

边界与易错点​

  • n < 2 不是质数，不能落入普通循环后误判为真。
  • 循环上界必须包含平方根；否则 49 会漏掉因子 7。
  • 不要以浮点 sqrt(n) 直接控制循环，使用 divisor <= n / divisor 同时规避舍入和乘法溢出。

模式迁移​

当任务从“判断一个数”变成“列出 1..n 的全部质数”时，重复试除会浪费结果，应迁移到线性筛。后续分解质因数也复用同样的安全试除边界。