最大公约数(GCD)和最小公倍数(LCM)

组别：提高级
难度：2

洛谷：P1029
OJ平台：P4248

最大公约数

方法一：遍历查找法
从a,b中小的哪个数开始，a, a-1, a-2…逐一查找，找到第一个满足同时被a,b整除的条件就终止。

/**************************************************************** 
 * Description: GCD loop
 * Author: Alex Li
 * Date: 2024-03-26 12:45:13
 * LastEditTime: 2024-03-26 12:50:16
****************************************************************/
#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    for(int i=min(a,b);i>1;i--){
        if(a%i==0&&b%i==0){
            cout<<i;
           break;
        }
    }
    return 0;    
}

方法二：辗转相减法

/****************************************************************
 * C++  用辗转向减法求最大公约数
 * date： 2022-5-2
 * verstion: 1.0
 * author: Alex Li
 ****************************************************************/ 

#include<iostream>
using namespace std;

int gcd(int a,int b){
    if(b==a)return a;
    if(a<b) swap(a,b);
    return gcd(b,a-b);
}

int  main(){
    int a,b;
    cout<<"input two number: ";
    cin>>a>>b;
    cout<<gcd(a,b);
        return 0;
}

方法三：欧几里德算法又叫辗转相除法。
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

例一：求26 和12两个整数的最大公约数
26/12=2(余2)
12/2=6(余0)
所以2为两数的最大公约数。
例二：求3139和2117的最大公约数
3139/2117=1(余1022)
2117/1022=2(余73)
1022/73=0
所以73为两数的最大公约数

递归方法

/****************************************************************
 * C++  用欧几里德算法求最大公约数
 * date： 2023-3-11
 * verstion: 1.2
 * author: Alex Li
 ****************************************************************/ 

#include<iostream>
using namespace std;

int gcd(int a,int b){
    if(a%b==0)return b;
    return gcd(b,a%b);
}

int  main(){
    int a,b;
    cout<<"input two number: ";
    cin>>a>>b;
    cout<<gcd(a,b);
        return 0;
    
}

递推方法

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main(){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
}

最小公倍数

方法一：直接遍历求解

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-13 12:55:11
 * 最后修改: 2025-01-13 13:01:52
 * 文件描述: 求最小公倍数
****************************************************************/
#include <iostream>
using namespace std;

// 直接遍历求最小公倍数
int lcm_direct(int a, int b) {
    int max_ab = max(a, b); // 从较大值开始检查
    int c = max_ab; // 逐步检查 max_ab 的倍数
    while (true) {
            if (c % a == 0 && c % b == 0) {
            return c; // 找到最小公倍数
        }
        c+=max_ab;
    }
}

int main() {
    int a, b;
    cout << "输入两个整数：";
    cin >> a >> b;
    cout << "最小公倍数是：" << lcm_direct(a, b) << endl;
    return 0;
}

方法二：公式法

在 C++ 中，计算两个整数的最小公倍数（LCM, Least Common Multiple）可以使用最大公约数（GCD, Greatest Common Divisor）的性质：

LCM(a,b)=\(\frac{∣a⋅b∣}{GCD(a,b)}\)

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-13 13:10:05
 * 最后修改: 2025-01-13 13:10:19
 * 文件描述: 利用最大公约数计算最大公倍数
****************************************************************/
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main(){
    int a,b;
    cin>>a>>b;
    cout<<a*b/gcd(a,b);
    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

最大公约数(GCD)和最小公倍数(LCM)