
(c++)求最大公约数
编写程序,求两个数的最大公约数(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≤2
编写程序,求两个数的最大公约数(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;
}
更多推荐
所有评论(0)