最大公约数(gcd())和最小公倍数(lcm())的c语言和c++详细解法

最大公约数(gcd())和最小公倍数(lcm())

最大公约数：

定义：

两个或多个整数共有的约数中最大的一个。
例如：整数12和18，他们的公约数有1、2、3、6，其中最大的公约数是6。

c语言解法：辗转相除法和更相减损法

1、辗转相除法:
思路：先求解较大的数除以较小的数的余数，再用较小的数除以前面求的余数，若求解下来的结果是0，则余数是最大公约数。
code：

#include <iostream>
using namespace std;
int a,b;
int c;
int r;
int main(){
    cin>>a>>b;
    if(a<b){
        c=a;
        a=b;
        b=c;
    }
    while(a>0){
        r=a%b;
        b=b/a;
        if(b==0){
            cout<<r<<endl;
            break;
        }
    }
}

2、更相减损法
思路：给定两个正整数，用较大的数减去较小的数，然后继续这个过程，直到得到两个相等的数，这个数就是这两个数的最大公约数。
code：

#include <iostream>
using namespace std;
int a,b;
int main(){
    cin>>a>>b;
    while(b!=0){
        if(a>b) a=a-b;
        else b=b-a;
    }
    cout<<a<<endl;
}

c++解法：gcd()函数

code:

#include <iostream>
#include <numeric>
using namespace std;
int main(){
    int b=12;
    int c=18;
    int a=gcd(b,c);
    cout<<a<<endl;
}

最小公倍数：

定义：

两个或多个整数的公倍数中最小的一个。
例如：整数12和18，他们的公倍数有36、72、108，其中最小公倍数是36。

c语言解法：使用最大公约数和直接求最小公倍数

1、使用最大公约数
思路：最小公倍数和最大公约数之间存在关系：两个数的乘积等于它们的最大公约数和最小公倍数的乘积。
code：

#include <iostream>
using namespace std;
int a,b;
int c;
int d;
int gcd(int x,int y){
    while(y!=0){
        if(x>y) x=x-y;
        else y=y-x;
    }
    return x;
}
int main(){
    cin>>a>>b;
    c=gcd(a,b);
    d=(a*b)/c;
    cout<<d<<endl;
}

2、直接求最小公倍数
思路：从两个数中较大的数开始，逐渐增加，直到找到一个数，它同时能被两个数整除。(效率低，不推荐使用)
code：

#include <iostream>
using namespace std;
int b,c;
int a(int x,int y){
    int max=(x>y) ? x : y;
    while(1){
        if(max%x==0&&max%y==0){
            return max;
        }
        max++;
    }
}
int main(){
    cin>>b>>c;
    int d=a(b,c);
    cout<<d<<endl;
}

c++解法：lcm()函数

code：

#include <iostream>
#include <numeric>
using namespace std;
int main(){
    int b=12;
    int c=18;
    int a=lcm(b,c);
    cout<<a<<endl;
}