困难C++6 分钟2,148 字

C++素数

判断素数——从分饼干到C++高效算法

素数(也叫质数)​ 是数学中一个神奇的概念。生活中,我们经常要分组分东西。比如6块饼干,可以分成2组每组3块,也可以分成3组每组2块,或者1组每组6块、6组每组1块——你看,它有很多种分法,除了“1组全部”和“每组1块”之外,还能有其他分法。 但有些数字就很“小气”,比如7块饼干,你只能分成1组每组7块,或者7组每组1块,再也找不到其他分组方式。这种只能被 1 和它本身 整除的大于1的自然数,就叫素数。最小的素数是2,它也是唯一的偶数素数。

在编程中,我们经常需要判断一个数是不是素数,比如用来加密、安排座位、分析数据等。下面我们就来学习如何用C++高效地判断素数。


关键概念讲解

1. 什么是“整除”和“因数”?

  • 整除:如果整数 a 除以整数 b(b≠0)的余数为0,我们就说 b 能整除 a,b 是 a 的一个因数。
  • 例子:12 ÷ 3 = 4 余0,所以3是12的因数;12 ÷ 5 = 2 余2,5不是12的因数。
  • 素数:大于1的自然数,它只有两个因数:1和它本身。比如7的因数只有1和7,所以7是素数。而6的因数有1、2、3、6,共4个,所以6不是素数(叫合数)。

2. 为什么检查到平方根就够了?

你可能会想:判断一个数 n 是不是素数,最笨的办法就是从2试到 n-1,看看有没有能整除的。但这样太慢了,尤其当 n 是1亿时,要检查近1亿次! 优化原理​​:如果 n 有一个大于 √n 的因数 a,那么它一定有一个小于 √n 的因数 b,因为 a × b = n,所以 b = n / a,且 b < √n。 例:判断 100 是不是素数。√100 = 10。只需检查210是否有因数。2能整除100,所以100不是素数。我们不需要检查20、25等,因为2已经在210里了。 所以只需从2检查到 √n 即可,大大减少循环次数。

3. 奇偶性优化

除了2以外,所有偶数都不是素数(因为它们都能被2整除)。所以我们先单独处理2,然后只检查奇数因子(从3开始,每次加2)。这样循环次数又减少一半。


代码深度讲解

下面是一段完整、高效的C++判断素数函数,每行都加了中文注释:

cpp
#include <iostream>   // 用于输入输出
#include <cmath>      // 用于 sqrt 函数
using namespace std;  // 标准命名空间

// 判断素数的函数,返回 true 表示是素数
bool isPrime(int n) {
    if (n < 2) return false;          // 小于2的数(0、1、负数)不是素数
    if (n == 2) return true;          // 2是素数,特例
    if (n % 2 == 0) return false;     // 其他偶数都不是素数

    int limit = sqrt(n);              // 计算 n 的平方根(取整数部分)
    for (int i = 3; i <= limit; i += 2) { // 只检查奇数因子
        if (n % i == 0) {            // 如果 i 能整除 n
            return false;            // 则 n 不是素数
        }
    }
    return true;                     // 循环结束都没找到因数,n 是素数
}

int main() {
    int num;                         // 定义变量,存储用户输入的数字
    cout << "请输入一个正整数:";
    cin >> num;                      // 读取输入
    if (isPrime(num)) {
        cout << num << " 是素数。" << endl;
    } else {
        cout << num << " 不是素数。" << endl;
    }
    return 0;                        // 程序正常结束
}

要点解释​​:

  • 第7行:n < 2 包括了0和1,它们既不是素数也不是合数,我们都返回 false。
  • 第8行:2是唯一的偶数素数,单独处理。
  • 第9行:排除所有大于2的偶数。
  • 第11行:提前把 sqrt(n) 赋值给 limit,避免每次循环都重复计算平方根(虽然编译器可能优化,但养成好习惯)。
  • 第12行:从3开始,步长为2,只检查奇数。注意 i <= limit 要取等号,比如 n=9,√9=3,需要检查i=3,才能发现9不是素数。
  • 第13-15行:如果能整除,立即返回 false。

常见错误与注意事项

  1. 忘记处理小于2的情况 新手常常只写 if (n == 1) return false; 却忘记0和负数。其实简洁写法 if (n < 2) 一次性排除所有。
  2. 循环条件写成 i < sqrt(n) 而不是 i <= sqrt(n) 这样会漏掉平方根恰好是因数的情况(如n=25,√25=5,需要检查i=5才能发现),导致错误判断25为素数。
  3. 使用浮点数平方根可能导致精度问题 sqrt(n) 返回 double,在 for 循环中比较 i <= sqrt(n) 时,由于浮点数精度误差,可能多算一次或少算一次。更稳妥的做法是:for (int i = 3; i * i <= n; i += 2)。用 i * i <= n 代替 i <= sqrt(n),避免浮点运算,同时更快(乘法比开方快)。 示例修改: for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) return false; }
  4. 忘记排除所有偶数因子 如果只写循环 i++,会检查2、4、6等偶数因子,虽然也能得到正确结果,但白白浪费一半时间。我们的优化从3开始 i += 2 就跳过了偶数。
  5. 把“因数”和“质因数”混淆 注意判断素数只关心是否存在​非1非自身的因数,不关心这些因数是不是素数。比如6的因数2是一个素数,但不影响6是合数。

完整可运行示例

下面是一个完整的程序,包含更详细的输出,可以多次输入(输入0退出):

cpp
#include <iostream>
#include <cmath>
using namespace std;

// 判断素数的函数
bool isPrime(int n) {
    if (n < 2) return false;          // 小于2的不是素数
    if (n == 2) return true;          // 2是素数
    if (n % 2 == 0) return false;     // 偶数(除2外)不是素数
    for (int i = 3; i * i <= n; i += 2) { // 只检查奇数因子,避免浮点数
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num;                         // 存储用户输入
    cout << "素数检测器(输入0退出)" << endl;
    while (true) {
        cout << "请输入一个正整数:";
        cin >> num;
        if (num == 0) {
            cout << "再见!" << endl;
            break;
        }
        if (isPrime(num)) {
            cout << num << " 是素数。" << endl;
        } else {
            cout << num << " 不是素数。" << endl;
        }
    }
    return 0;
}

测试示例​​:

  • 输入 2 → 素数
  • 输入 1 → 不是素数
  • 输入 17 → 素数
  • 输入 100 → 不是素数
  • 输入 0 → 退出

相关知识点指引

  • 埃拉托斯特尼筛法​​:当需要判断很多个数​是不是素数时(比如2到100万),逐个用 isPrime 太慢,可以用“筛子”一次性找出所有素数,效率极高。
  • 分解质因数​​:将一个合数拆成多个素数相乘的形式,比如 12 = 2×2×3。与判断素数思路相反。
  • 数学性质​​:除了2和3,所有素数都能写成 6k±1 的形式(但反过来不成立)。可以用这个性质进一步优化循环步长。

掌握了判断素数的方法,你就拿到了很多数论算法的基础钥匙。下次遇到“密码学”中的RSA算法,你会发现它本质上就是依赖大素数难以分解的特性。继续加油探索吧!

同类知识点