- C++
C++ 五级质因数分解
- @ 2026-10-28 22:12:39
C++ 质因数分解 完整教程
一、什么是质因数分解?
质因数分解:把一个正整数拆成若干个质数相乘的形式。
例:,其中 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; |
七、复杂度
- 时间复杂度:
- 输入 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 条评论
目前还没有评论...