C语言 公约数辗转相除法

Question

main() { int num1,num2,temp; int a=0,b=0; //用int a,b;不太好，没有初始化。 printf("请输入两个数:"); scanf("%d%d",&num1,&num2); if(num1<num2) //保证了后面a的数比b大 { temp=num1; num1=num2; num2=temp; } a=num1; b=num2; while(b!=0) { temp=a%b; a=b; b=temp;//使用了辗转相除法 } printf("最大公约数是:%d\n",a); prinft("最小公倍数是:%d\n",num1*num2/a); } 我运行了好几遍 不过就是看不明白 辗转相除法是怎么使公约数得出来 谁能解释下呢

Answer 1

如果两个数有最大公约数A，那么这两个数，以及这两个数的差，还有大数除以小数的余数，必然都是A的倍数。
所以当最后两个数刚好能整除时，较小的数就是最大公约数。
建议你单步调试
深刻理解。。
下面是更加具体的：
对于两个数,我们要求是正整数,我们一般用辗转相除法两个数的最大公约数,下面我来仔细讲讲辗转相除法两个数的最大公约数的原理.
我们假设这两个数分别是X,Y,他们最大的公约数为M,则有X=a*M,Y=b*M(a,b是互质的数),很明显,我们的目的就是要把M的系数降到一,为此我们进行X%Y运算,实际上X%Y=(a%b)*M,由于a%b小于b,所以M的系数将会减小,接着我们进行Y%((a%b)*M)=(b%(a%b))*M,同理,则有b%(a%b)<(a%b),可见随着这样取余的操作M的系数会越来越小,前面已经说过,我们的目标是使M的系数降到一,而一是任何整数的约数,换句话说任何整数除一取余后为0,所以当取余之后的数为0,也就意味着M之前的系数为1,此时的被除数就是最大公约数,
举个例子
24
与
15
24=8*3
15=5*3
24%15=(8%5)*3=3*3=9;
15%9=(5%3)*3=2*3=6
9%6=(3%2)*3=3
6%3=(2%1)*3=0
-------------------------------被除数3就是24与5的最大公约数
两个正整数的最大公约数求出来之后他们的最小公倍数也就知道了,最小公倍数=两个数相乘除以他们的最大公约数,
原理很简单,不加详述.
在
C++中,求最大公约数的代码如下
int
gys(int
a,int
b)
//a必须要大于b
{
int
r=a%b;
while(r!=0)
{
a=b;
b=r;
r=a%b;
}
return
b;
}
求最小公倍数的代码很简单,如下
int
gbs(int
a,int
b)//a必须要大于b
{
return
a*b/gys(a,b);
}
好了,有错误之处还请指正