请解释一下这个“求最大公约和最小公倍”的程序

main()
{int a,b,num1,num2,temp;
printf("please input two numbers:\n");
scanf("%d,%d",&num1,&num2);
if(num1<num2)/*交换两个数，使大数放在num1上*/
{temp=num1;num1=num2;num2=temp;}
a=num1;b=num2;
while(b!=0)/*利用辗除法，直到b为0为止*/
{temp=a%b;a=b;b=temp;}
printf("gongyueshu:%d\n",a);
printf("gongbeishu:%d\n",num1*num2/a);
}

1.为什么交换两个数：num1和num2
2.什么叫“辗除法”，为什么用这个方法？
谢谢

12 个解决方案

#1

1.使num1>num2，其实这是习惯而矣，不换也行的
2.辗转相除是求最大公约数的最快方法

#2

if(num1<num2)/*交换两个数，使大数放在num1上*/
{temp=num1;num1=num2;num2=temp;}
a=num1;b=num2;

改为：
a = ((num1>num2) ? num1 : num2);
b = ((a==num1) ? num2 : num1);
这样就不必交换 num1 和 num2 了

#3

展转法就是不断的除

#4

请参看《计算机程序设计艺术》的第一章，算法步骤我不再说了，我只讲讲理论好了。
如果两个数分别为m,n（m>n)，那么让m除以n，如果余数为0，那么最小公倍数就是n（小学生也知道）。但是不为0的话，那么可以这样写m=qn+r，其中q为整数，r为余数。注意，在这种情况下，（设x为m,n的最小公倍数）x若是可以整除m和n，那么它也一样可以整除n和r，那么，就可以用展转的方法来替代了m,n了。

#5

那么可以这样写m=qn+r，其中q为整数，r为余数。注意，在这种情况下，（设x为m,n的最小公倍数）x若是可以整除m和n，那么它也一样可以整除n和r，
怎么证明x可以整除r？？？？！？

#6

交换是要求大数除以小数么
辗转相除就是交换除数与被除数进行除法运算

#7

summer6074(买一送2）
我想到一种假设，如果m=11,n=3
那么，q=3，此时r=2，而m,n的最小公倍数为33，好像不能整除r啊？！！！

#8

summer6074(买一送2）讲的不是最小公倍数,而是最大公约数.

#9

谢谢楼上的，那天我看错了，谢谢啊！

#10

参见华罗庚《数论导引》。

#11

还不太明白
能否说得详细明白些？

#12

其实这种算法的东西,最好是 debug 一下就很清楚了

#1