最大公约数

一、辗转相除法
1,循环除

#include <iostream>
using namespace std;
int main(){
    int a,b,t;
    cin>>a>>b;
    if(a<b)swap(a,b);
    do{
        t=a%b;
        a=b;
        b=t;
    }while(t);
    cout<<a<<endl;
    return 0;
}

2,迭代除

#include <iostream>
using namespace std;
int gcd(int a,int b){
    if(b==0)
        return a;
    return gcd(b,a%b);
}

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

扩展:a,b最小公倍数=(ab最大公约数^2)a/最大公约数b/最大公约数=a*b/最大公约数

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容