• C++
  • C++ 五级质因数分解

  • @ 2026-10-28 22:12:39

C++ 质因数分解 完整教程


一、什么是质因数分解?

质因数分解:把一个正整数拆成若干个质数相乘的形式。

例:12=2×2×312 = 2 \times 2 \times 3,其中 2、3 都是质数,所以 2、2、3 就是 12 的质因数。

质数:大于 1 的自然数,除了 1 和它本身没有其他因数。

数字 是不是质数 原因
2 ✅ 只能被 1 和 2 整除
3 只能被 1 和 3 整除
4 ❌ 4 = 2 × 2
9 9 = 3 × 3
17 ✅ 只能被 1 和 17 整除

二、核心思路(小学生也能懂)

拿 12 举例,分解过程就像"反复除":

第1步:12 ÷ 2 = 6   → 记下一个 2
第2步: 6 ÷ 2 = 3   → 再记下一个 2
第3步: 3 ÷ 2 除不尽,换 3 试:3 ÷ 3 = 1 → 记下一个 3
除到结果变成 1 了,结束!

所以:12 = 2 × 2 × 3

关键规则:从最小的质数 2 开始试除,能除尽就一直除,除不尽就换下一个数。因为小的因数都除干净了,后面除出来的一定是质数,不用额外判断。


三、完整代码(带逐行注释)

#include <iostream>
using namespace std;

int main()
{
    long long n;          // 用 long long 防止大数溢出,最多能处理到 9×10^18
    cout << "请输入一个正整数:";
    cin >> n;

    cout << n << " = ";

    // ========== 第一步:处理所有的因数 2 ==========
    // 只要 n 还能被 2 整除,就一直除下去
    while (n % 2 == 0)   // n % 2 == 0 意思是 "n 除以 2 余数为 0"
    {
        cout << 2;       // 输出一个质因数 2
        n = n / 2;       // 把 n 除以 2,去掉这个因数
        if (n > 1) cout << " × ";  // 如果还没除完,输出乘号连接
    }

    // ========== 第二步:从 3 开始试除奇数 ==========
    // i 从 3 开始,每次加 2(只试奇数,因为偶数已经被第一步除光了)
    // 循环条件:i * i <= n,意思是试到 √n 就够了(后面会讲为什么)
    for (long long i = 3; i * i <= n; i += 2)
    {
        // 只要 i 还能整除 n,就一直除
        while (n % i == 0)
        {
            cout << i;   // 输出这个质因数
            n = n / i;   // 去掉这个因数
            if (n > 1) cout << " × ";
        }
    }

    // ========== 第三步:处理最后剩下的大质数 ==========
    // 如果最后 n 还大于 2,说明剩下的 n 本身就是一个质数
    // 比如分解 13:前两步都除不动,最后剩下 13,它自己就是质因数
    if (n > 2)
    {
        cout << n;
    }

    cout << endl;
    return 0;
}

四、逐段详细讲解

1. 为什么要单独处理 2?

2 是唯一的偶质数。把所有的 2 除干净之后,剩下的数一定是奇数,后面就只需要试奇数(3、5、7、9…),一下省掉一半的计算量。

n = 12
除 2:12 → 6 → 3   (除了两次 2)
剩下 3,是奇数,后面只试奇数就行

2. 为什么循环条件是 i * i <= n?

这是整个算法最核心的优化。

道理:如果 n 有一个大于 √n 的因数,那它一定配对一个小于 √n 的因数。小的那个早就被我们找到了,所以试到 √n 就足够了。

例:n = 36 √36 = 6 36 的因数对:(2,18) (3,12) (4,9) (6,6) 所有因数里,小的那个(2、3、4、6)都 ≤ 6,试到 6 就够了,不用试到 35。

省了多少?

  • 暴力试到 n:要试 1000 次(n=1000 时)
  • 试到 √n:只需要试 31 次

3. 为什么第三步要单独判断 n > 2?

两种情况:

情况 举例 结果
n 本身是质数 输入 17 前两步都除不动,最后 n 还是 17,直接输出 17
分解完了 输入 12 最后 n 变成 1,不输出任何东西

五、运行效果示例

请输入一个正整数:12
12 = 2 × 2 × 3
请输入一个正整数:100
100 = 2 × 2 × 5 × 5
请输入一个正整数:17
17 = 17
请输入一个正整数:999999937
999999937 = 999999937

(这个数本身是个大质数,所以直接输出自己)


六、常见错误提醒

错误写法 问题 正确做法
int n 大数会溢出 用 long long n
i <= n 太慢,大数会卡 改成 i * i <= n
忘了 while 只写 if 一个因数只除一次,除不干净 用 while 反复除直到除不动
没处理最后剩下的 n 漏了最后那个大质数 最后加 if (n > 2) cout << n;

七、复杂度

  • 时间复杂度:O(n)O(\sqrt{n})
  • 输入 10^9 只需要试 3 万多次,瞬间出结果
  • 输入 10^12 也只需要试 100 万次,完全扛得住

去掉单独处理 2 的步骤,统一从 2 开始循环,代码更简洁。

改写后完整代码

#include <iostream>
using namespace std;

int main()
{
    long long n;
    cout << "请输入一个正整数:";
    cin >> n;

    cout << n << " = ";

    // 从 2 开始,一直试除到 √n
    // i*i <= n 是核心优化:试到平方根就够了
    for (long long i = 2; i * i <= n; i++)
    {
        // 只要 i 能整除 n,就一直除
        while (n % i == 0)
        {
            cout << i;       // 输出这个质因数
            n = n / i;       // 把 n 里的 i 因子除掉
            if (n > 1) cout << " × ";  // 没除完就乘号连接
        }
    }

    // 最后如果 n 还大于 1,说明剩下的 n 本身就是一个质数
    if (n > 1)
    {
        cout << n;
    }

    cout << endl;
    return 0;
}

两种写法对比

先单独除2版 统一循环版(现在这个)
代码行数 多一点 更短更简洁
循环步进 i += 2(只试奇数) i++(每个数都试)
速度 快一倍 慢一点点
教学理解 要分两步讲 一个逻辑走到底,好讲

多试的那些偶数会不会出错? 不会。因为 2 一旦除干净了,后面的 4、6、8... 再怎么试都除不动,空转一圈而已,结果完全正确,只是多花一点点时间。


运行效果(一模一样)

请输入一个正整数:12
12 = 2 × 2 × 3
请输入一个正整数:100
100 = 2 × 2 × 5 × 5
请输入一个正整数:97
97 = 97

这种统一写法上课讲最顺:就一个 for 循环 + while 反复除 + 最后兜个底,学生记一个模式就行。

0 条评论

目前还没有评论...