一文讲清计算质因数分解，最大公约数，最小公倍数的方法

质因数、最大公约数与最小公倍数：原理与C++实现

尔辈需究物理

一、核心原理剖析

1.1 质因数：

定义：把一个正整数分解为若干个质数相乘的形式，这些质数就是该数的质因数。 简单来说，质因数就是构成一个数的“最小质数单元”。

示例： 21 = 3 × 7（3和7是21的质因数） 60 = 2 × 2 × 3 × 5（2、3、5是60的质因数） 90 = 2 × 3 × 3 × 5（2、3、5是90的质因数）

1.2 最大公约数（GCD）：两数的“最大公共除数”

先理清基础概念，再看核心定义：

  • 约数：能整除某数的正整数（如6的约数是1、2、3、6，注意：1是所有正整数的约数）；
  • 公约数：能同时整除两个（或多个）数的正整数（如6和12的公约数是1、2、3、6）；
  • 最大公约数：公约数中数值最大的那个数（如6和12的最大公约数是6，而非原内容中的12）。

核心特征：两个数的最大公约数，是它们所有公共质因数的乘积。 > 示例：6（2×3）和12（2×2×3）的公共质因数是2和3，因此GCD(6,12)=2×3=6。

1.3 最小公倍数（LCM）：两数的“最小公共倍数”

定义：能被两个（或多个）数同时整除的最小正整数。

核心公式（仅适用于两个数）： 对于正整数a和b，满足： a × b = GCD(a, b) × LCM(a, b) 由此可推导出最小公倍数的计算方法：

示例：计算6和12的最小公倍数 GCD(6,12)=6，因此LCM(6,12)=(6×12)/6=12。

二、实践落地：C++代码实现

2.1 质因数分解

功能说明

将一个正整数分解为质因数相乘的形式，处理边界条件（如输入为1），并优化循环性能。

优化后代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cmath> // 用于sqrt函数（可选，优化循环）
using namespace std;

// 质因数分解函数（封装成函数，更易复用）
void primeFactorization(int num) {
    if (num < 1) { // 处理非正整数输入
        cout << "请输入正整数！" << endl;
        return;
    }
    
    int original_num = num; // 保存原始数值，用于输出
    cout << original_num << " = ";
    
    // 边界条件：1既不是质数也不是合数，无质因数
    if (num == 1) {
        cout << "1" << endl;
        return;
    }
    
    bool isFirstFactor = true; // 控制乘号输出，避免开头/结尾多余符号
    
    // 优化：循环到sqrt(num)即可，减少遍历次数
    for (int i = 2; i <= sqrt(num); i++) {
        // 若i是质因数，循环提取（处理重复因数，如12=2×2×3）
        while (num % i == 0) {
            if (!isFirstFactor) {
                cout << " × "; // 非第一个因数，先输出乘号
            }
            cout << i;
            num /= i; // 缩小num，继续分解
            isFirstFactor = false;
        }
    }
    
    // 处理剩余的质数（如15分解后剩余的5，23这类质数本身）
    if (num > 1) {
        if (!isFirstFactor) {
            cout << " × ";
        }
        cout << num;
    }
    
    cout << endl;
}

int main() {
    int num;
    cout << "请输入需要分解质因数的正整数：";
    cin >> num;
    primeFactorization(num);
    return 0;
}

代码说明

  • 边界处理：新增非正整数、输入为1的判断，避免程序异常；
  • 性能优化：循环仅遍历到sqrt(num)，因为一个数的质因数不会超过其平方根；
  • 输出优化：用isFirstFactor控制乘号，避免出现“12 = × 2 × 2 × 3”这类错误格式；
  • 复用性：将分解逻辑封装为函数，便于后续调用。

运行示例

1
2
3
4
5
6
7
8
输入：90
输出：90 = 2 × 3 × 3 × 5

输入：1
输出：1 = 1

输入：7（质数）
输出：7 = 7

2.2 最大公约数（GCD）：辗转相除法

辗转相除法（欧几里得算法）是计算GCD的最优方法，核心逻辑：GCD(a,b) = GCD(b, a%b)，直到余数为0，此时的除数即为最大公约数。

迭代版，无栈溢出风险

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdlib> // 用于abs函数（处理负数）
using namespace std;

// 计算两个数的最大公约数（迭代版）
int gcd(int a, int b) {
    // 处理负数：取绝对值（公约数为正）
    a = abs(a);
    b = abs(b);
    
    // 核心循环：余数不为0时，持续更新被除数和除数
    while (b != 0) {
        int remainder = a % b; // 计算余数
        a = b;                 // 除数变为新的被除数
        b = remainder;         // 余数变为新的除数
    }
    return a; // 余数为0时，a即为最大公约数
}

int main() {
    int num1, num2;
    cout << "请输入两个整数（用空格分隔）：";
    cin >> num1 >> num2;
    
    int result = gcd(num1, num2);
    cout << num1 << " 和 " << num2 << " 的最大公约数是：" << result << endl;
    return 0;
}

递归版（简洁，但大数可能导致栈溢出）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdlib>
using namespace std;

// 计算两个数的最大公约数（递归版）
int gcdRecursive(int a, int b) {
    a = abs(a);
    b = abs(b);
    if (b == 0) { // 递归终止条件：余数为0
        return a;
    }
    return gcdRecursive(b, a % b); // 递归调用，更新参数
}

int main() {
    int num1, num2;
    cout << "请输入两个整数（用空格分隔）：";
    cin >> num1 >> num2;
    
    int result = gcdRecursive(num1, num2);
    cout << num1 << " 和 " << num2 << " 的最大公约数是：" << result << endl;
    return 0;
}

运行示例

1
2
3
4
5
输入：6 12
输出：6 和 12 的最大公约数是：6

输入：15 25
输出：15 和 25 的最大公约数是：5

2.3 最小公倍数（LCM）：基于GCD的计算

优化后代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdlib>
using namespace std;

// 先实现GCD函数（依赖）
int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

// 基于GCD计算最小公倍数
int lcm(int a, int b) {
    if (a == 0 || b == 0) { // 边界：0没有公倍数
        cout << "输入不能为0！" << endl;
        return -1;
    }
    // 先算GCD，避免a*b溢出（优化：(a/gcd(a,b))*b）
    return (a / gcd(a, b)) * b;
}

int main() {
    int num1, num2;
    cout << "请输入两个正整数（用空格分隔）：";
    cin >> num1 >> num2;
    
    int result = lcm(num1, num2);
    if (result != -1) {
        cout << num1 << " 和 " << num2 << " 的最小公倍数是：" << result << endl;
    }
    return 0;
}

代码说明

  • 溢出优化：将a*b/gcd(a,b)改为(a/gcd(a,b))*b，避免两个大数相乘导致的整数溢出；
  • 边界处理：新增输入为0的判断，因为0没有公倍数；
  • 依赖复用：直接复用已实现的GCD函数，符合“代码复用”最佳实践。

运行示例

1
2
3
4
5
输入：6 12
输出：6 和 12 的最小公倍数是：12

输入：15 25
输出：15 和 25 的最小公倍数是：75

三、实战练习：洛谷题目（U652633）

https://www.luogu.com.cn/problem/U652633 结合上述知识点，可完成洛谷题目U652633（质因数分解），以下是适配题目的优化代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int num, original_num;
    cin >> num;
    original_num = num;
    
    // 题目核心边界：输入1时直接输出1
    if (num == 1) {
        cout << 1 << endl;
        return 0;
    }
    
    bool firstFactor = true;
    // 优化循环：i*i <= num，减少遍历次数
    for (int i = 2; i * i <= num; i++) {
        while (num % i == 0) {
            if (!firstFactor) {
                cout << "×"; // 题目要求的乘号格式
            }
            cout << i;
            num /= i;
            firstFactor = false;
        }
    }
    
    // 处理剩余的质数
    if (num > 1) {
        if (!firstFactor) {
            cout << "×";
        }
        cout << num;
    }
    
    cout << endl;
    return 0;
}

事项

  1. 性能优化：质因数分解时，循环到sqrt(num)而非num，时间复杂度从O(n)降至O(√n)；
  2. 边界条件：务必处理输入为1、0、负数的情况，避免程序逻辑错误；
  3. 溢出问题：计算LCM时，优先做除法再乘法，避免整数溢出（如(a/gcd)*b而非a*b/gcd）。