提示:采用辗转取余算法。m除以n的余数为零,则n为最大公约数;余数不为零,则将n付给m,余数赋给n,在重复上述操作,直到余数为零为止···
注明解释··谢谢···
代码及注释如下:
#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)。
因而,可以由此,得到两个数的最大公约数。