1020: 求两整数的最大公约数和最小公倍数

逃离我推掉我的手 2023-01-10 09:54 146阅读 0赞

## Description ##

输入两个正整数m和n，求其最大公约数和最小公倍数。

## Input ##

两个整数

## Output ##

最大公约数，最小公倍数

## Sample Input ![5f8f312f51791b8bb0ed0ae07c2ffa43.gif][] ##

5 7

## Sample Output ##

1 35

## Code ##

#include<iostream>
    #include<stdio.h>
    using namespace std;
    ///最大公约数辗转相除法
    int gcd(int a,int b)
    {
        int c;
        while(b!=0)
        {
            c=a%b;
            a=b;
            b=c;
        }
        return a;
    }
    ///最小公倍数即乘积除以最大公约数
    int lcm(int a,int b)
    {
        int k=gcd(a,b);
        return a*b/k;
    }
    int main()
    {
        int a,b;
        cin>>a>>b;
        int A=gcd(a,b);
        int B=lcm(a,b);
        cout<<A<<" "<<B<<endl;
        return 0;
    }

本题使用的是辗转相除法求最大公约数，还可以使用两种方法

[https://blog.csdn.net/Zhang\_1218/article/details/73196314?utm\_medium=distribute.pc\_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control&depth\_1-utm\_source=distribute.pc\_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control][https_blog.csdn.net_Zhang_1218_article_details_73196314_utm_medium_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control_depth_1-utm_source_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control]

最大公约数是[greatest common divisor][]（GCD）

最小公倍数是[least/lowest common multiple][least_lowest common multiple]（LCM）

[5f8f312f51791b8bb0ed0ae07c2ffa43.gif]: /images/20221119/c50650856ef64e678e3f7b8760d6060e.png
[https_blog.csdn.net_Zhang_1218_article_details_73196314_utm_medium_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control_depth_1-utm_source_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control]: https://blog.csdn.net/Zhang_1218/article/details/73196314?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control
[greatest common divisor]: http://www.baidu.com/link?url=6F3-soiEUdfBpfakZp1QrECDtzS0yPpaFQirBH5_mXOjsRZ0C7cL35WIjRRZqYcqRFGBciduxNl-g2qVWXguhDC9EexFKm-s2UhZYf5x9lHWQmxBjKRxllXsBLiPVA5A
[least_lowest common multiple]: http://www.baidu.com/link?url=DDz-3VyCXpWmRvwANiAwFEBCrbj1l0_jSvvsr7MNfsn8AF_Qsc5__4MQPSNWuun5VH-W8C9vmnGDFSHwOg5HCrjrtjAODmzMf4OA5B1Alk-olwt_310fQbv92G-Pb14B537tAigCeH3LH2X-sOvHma