编写程序,求两个数的最大公约数(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≤2
30
, 0≤B≤2
30
。
输出格式:
输出 A 和 B 的最大公约数。
输入样例:
#include <stdio.h>
int main()
{
int m = 0;
int n = 0;
int r = 0;
scanf("%d %d",&m,&n);
while(r=m%n)
{
m = n;
n = r;
}
printf("%d\n",n);
return 0;
}
#include <stdio.h>
int gcd(int m,int n)
{
if(!n)return m;
return gcd(n,m%n);
}
int main()
{
int m,n;
printf("请输入2个正整数:");
while(1)
{
scanf("%d%d",&m,&n);
if(m<=0||n<=0)printf("输入了非正整数!!!\n请重新输入:");
else break;
}
printf("这两个正整数的最大公约数为:%d\n",gcd(m,n));
return 0;
}