C++ 判断素数

素数也叫 “质数”，指的是大于 1，并且除了 1 和它本身以外，不能被其他正整数整除的整数。例如 2、3、5、7 都是素数，而 4 不是素数，因为 4 除了能被 1 和 4 整除，还能被 2 整除。

在动手写代码之前，我们需要先明确一条基本规则：1 不是素数，最小的素数是 2。因此所有小于 2 的整数（包括负数、0 和 1）都不是素数，可以直接排除。

如何使用试除法判断素数？

在 C++ 中，判断整数 n 是否为素数最直接的思路，就是使用 for 循环从 2 开始一个个试着去做除法，这种方法通常称为 “试除法”。下面我们分两步把判断逻辑理清楚。

1. 从 2 开始逐个试除

排除小于 2 的整数之后，我们可以让除数 i 从 2 开始依次递增，通过 n % i == 0 检查 n 能否被 i 整除。一旦在循环过程中发现某个 i 能整除 n，说明除了 1 和 n 本身之外还存在其他因子，此时就能断定 n 不是素数，直接返回 false 结束判断。

反过来，如果我们把所有需要检查的除数 i 都试除了一遍，始终没有找到能整除 n 的数，就说明它没有额外因子。此时等循环结束后，直接返回 true 即可。

2. 为什么只需检查到平方根？

很多初学的小伙伴第一次写试除法时，会把循环条件写成 i < n。比如判断 97 是不是素数，就让程序从 2 一直试除到 96。这种写法虽然结果没错，但做了大量多余的检查。

其实，如果一个合数有额外因子，这些因子一定是成对出现的。不妨以 36 为例，它的平方根是 6，相乘等于 36 的因子对如下：

36 = 2 * 18
36 = 3 * 12
36 = 4 * 9
36 = 6 * 6

观察左边这一列较小的因子 2、3、4、6 可以发现，它们全都小于或等于平方根 6。道理很简单：如果两个因子都大于 n 的平方根，它们乘起来的结果必然会超过 n，这是不可能的。

换句话说，只要从 2 检查到 n 的平方根都没有找到能整除 n 的因子，那么平方根后面也肯定不会再有因子了。既然较小的因子 i 不会超过 n 的平方根，我们在循环条件里直接判断 i * i <= n 即可。下面 2 种方式是等价的。

// 方式 1（推荐）
for (int i = 2; i * i <= n; i++) {
    // 检查能否整除
}

// 方式 2
for (int i = 2; i < n; i++) {
    // 检查能否整除
}

其中，方式 1 只检查到平方根附近，当 n 比较大时循环次数远少于方式 2，因此在实际开发中我们更推荐使用方式 1。

C++ 判断单个素数

理清试除规则与循环边界后，我们把这套逻辑写成返回布尔值的 isPrime() 函数，并在 main() 函数中测试 1、2、9、17 这 4 个典型数字。

示例 1：定义 isPrime() 判断素数

#include <iostream>

// 判断整数 n 是否为素数
bool isPrime(int n) {
    if (n < 2) {
        return false;        // 小于 2 的数不是素数
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;    // 找到额外因子，不是素数
        }
    }
    return true;             // 全部试除完仍无因子，是素数
}

int main() {
    std::cout << "1 是否为素数：" << (isPrime(1) ? "是" : "否") << '\n';
    std::cout << "2 是否为素数：" << (isPrime(2) ? "是" : "否") << '\n';
    std::cout << "9 是否为素数：" << (isPrime(9) ? "是" : "否") << '\n';
    std::cout << "17 是否为素数：" << (isPrime(17) ? "是" : "否") << '\n';
    return 0;
}

运行结果如下。

1 是否为素数：否
2 是否为素数：是
9 是否为素数：否
17 是否为素数：是

分析：

从运行结果可以看出，1 和 9 被判定为非素数，2 和 17 被判定为素数。函数开头的 if (n < 2) 用来过滤小于 2 的整数，因此传入 1 时直接返回 false。当我们传入最小的素数 2 时，循环变量 i 初值为 2。由于 2 * 2 = 4 大于 2，i * i <= n 不成立，程序跳过循环直接返回 true。

当我们传入 17 时，因为 4 * 4 = 16、5 * 5 = 25，所以 i 依次取 2、3、4，试除 3 次后返回 true。另外，在 std::cout 中使用三元运算符打印 "是" 或 "否" 时，记得用小括号把整个条件表达式括起来（否则会因 << 优先级更高而报错）。

这里小伙伴们要特别留意，循环条件 i * i <= n 中的等号不能漏掉。比如传入完全平方数 9 时，i 递增到 3 刚好满足 3 * 3 <= 9，从而测出 9 % 3 == 0 并返回 false。一旦漏掉等号写成 i * i < n，程序在 i = 3 时就会提前跳出循环，把 9 误判成素数。

此外，有些小伙伴在写循环里的条件判断时，容易顺着 if...else 语句的习惯，直接在 if 后面补上一个 else 分支。注意区分下面这两种写法：

// 正确方式
for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        return false;
    }
}
return true;

// 错误方式
for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        return false;
    } else {
        return true;
    }
}

对于这一点，小伙伴们可别搞混了：找到一个能整除 n 的因子，就能立刻断定它不是素数；但仅仅不能被某一个数整除，并不能说明它就是素数。

比如奇数 9 在第 1 轮检查 9 % 2 时余数不为 0，如果写了 else 分支就会马上返回 true，根本没机会继续检查后面的 i = 3。因此，我们必须等循环把平方根以内的除数全部检查完，才能在循环外面执行 return true;。

找出 1~50 之间的所有素数

有了上面写好的 isPrime() 函数，如果我们想把 1~50 之间的所有素数找出来，只需要在 main() 函数中配合一个循环逐个判断即可。

示例 2：输出 1~50 之间的素数

#include <iostream>

bool isPrime(int n) {
    if (n < 2) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    std::cout << "1~50 之间的素数有：\n";
    for (int n = 1; n <= 50; n++) {
        if (isPrime(n)) {
            std::cout << n << " ";
        }
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

1~50 之间的素数有：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

分析：

把判断单个整数的逻辑放进 isPrime() 函数后，main() 函数就清爽多了：只需让 n 从 1 遍历到 50，每当 isPrime(n) 返回 true 就打印当前的 n。如果想进一步统计素数个数，我们还可以在循环前定义 int count = 0;，每次满足条件时执行 count++ 即可。