C语言编程：输入两个正整数m和n，求它们的最大公约数。

Question

提示：采用辗转取余算法。m除以n的余数为零，则n为最大公约数；余数不为零，则将n付给m，余数赋给n，在重复上述操作，直到余数为零为止···

注明解释··谢谢···

Answer 1

代码及注释如下：

#include <stdio.h>

int GCD(int a,int b)//定义函数，用来计算最大公约数

{    

return b==0?a:GCD(b,a%b);

//此处使用了递归，如果b=0,返回a为最大公约数，否则，一直以b与a%b赋给函数，实现辗转相除

}

int main()

{

int a, b ; //定义实参a, b

int answer ; //定义最后结果

scanf ( "%d%d" , &a, &b) ; //取a，b的值

answer = GCD (a, b) ; //把结果赋给answer

printf ( "%d与%d的最大公约数为%d\n" , a , b , answer ) ; //输出结果

}

扩展资料：

辗转相除法求最大公约数的原理：

因为对任意同时整除a和b的数u，有a=su，b=tu，它也能整除r，因为r=a-bq=su-qtu=(s-qt)u。

反过来每一个整除b和r的整数v，有 b=sv , r=tv，它也能整除a，因为a=bq+r=svq+tv=(sq+t)v。

因此a和b的每一个公因子同时也是b和r的一个公因子，反之亦然。

这样由于a和b的全体公因子集合与b和r的全体公因子集合相同，所以a和b的最大公因子必须等于b和r的最大公因子，这就证明了上边的等式。即(a,b)=(b,r)。

因而，可以由此，得到两个数的最大公约数。

Answer 2

main()
{
int a,b,num1,num2,temp;
printf("请输入两个正整数:\n");
scanf("%d,%d",&num1,&num2);
if(num1<num2)/*选出较大数*/
{
temp=num1;
num1=num2;
num2=temp;
}
a=num1,b=num2;
while(b!=0)/*辗转取余算法*/
{
temp=a%b;
a=b;
b=temp;
}
printf("它们的最大公约数为:%d\n",a);
printf("它们的最小公倍数为:%d\n",num1*num2/a);/*两数相乘除最大公约数就是最小公倍数*/
}本回答被提问者采纳

Answer 3

比较简单的做法

#include "stdio.h"
void main()
{
int num1,num2;
printf("请输入两个正整数:\n");
scanf("%d%d",&num1,&num2);

while(num1 != num2)//当两数不等时，不停的用大数减小数，并把结果赋值给大数，相当于求余数
if(num1>num2)
num1 = num1-num2;
else
num2=num2-num1;

printf("他们的最大公约数是%d",num1);
}

Answer 4

//这种方法更简单,算法上运行效率更高，本人试过
inline int gcd(int m,int n)
{
while(m!=n)
{
if(m>n) m-=n;
if(m<n) n-=m;
}
return m;
}
下面调用gcd(,)函数就ok了

Answer 5

#include <stdio.h>
void main()
{
int a, b, c;

printf("请输入两个整数：");
scanf("%d%d", &a,&b);
c = a%b;
while(c) {
if(c) {
a = b;
b = c;
}
c = a % b;
}
printf("最大公约数：%d", b);
}
// 输入 20 60；输出 20