编写程序,求两个数的最大公约数(GCD),例如:12 和 28 的最大公约数是 4。

求最大公约数的经典算法是欧几里德(Euclid)算法,方法如下。分别让变量 m 和 n 存储两个数的值。如果 n 为 0,那么停止操作,m 中的值就是 GCD;否则,计算 m 除以 n 的余数 r,把 n 保存到 m 中,并把余数 r 保存到 n 中。然后重复上述过程,每次都先判定 n 是否为 0。

输入格式:

在一行中给出 2 个整数 A 和 B,其中 0≤A≤230, 0≤B≤230。

输出格式:

输出 A 和 B 的最大公约数。

输入样例:

12 28
输出样例:

4

#include <iostream>
using namespace std;
int main ()
{
    int m,n,r;
    cin>>m>>n;
    if(n==0)
        cout<<m<<endl;
    else
    {   while(n!=0)
        {r=m%n;
         m=n;
         n=r;
        }
    }
     cout<<m<<endl;
    return 0;

Logo

腾讯云面向开发者汇聚海量精品云计算使用和开发经验,营造开放的云计算技术生态圈。

更多推荐