C语言 辗转相除法求最大公约数和最小公倍数
1、总述：求最大公约数和最小公倍数可以分为四步，先罗列出一些关键步骤。
2、第一步：输入数据
核心步骤为：
printf("请输入两个正整数，用逗号间隔：");
scanf("%d,%d",&x,&y);
3、第二步：比较大小
由于辗转相除是不断通过余数来作为除数的，所以刚输入的数据，一定是大除以小。为了保证数据的严密，需要比较调整一下两数大小。
核心步骤为：
if (a<b)
{
c=a;
a=b;
b=c;
}
保证了a>=b。
4、第三步：辗转相除求最大公约数
虽然辗转相除法是C语言的入门，但是我觉得其数学理论还是需要看的。这样才不会死记硬背，才能理解。只有准确理解了最大公约数的概念，才不会编出一个求出最小公约数的程序。
约数的概念为：
一对正整数a，b；存在c，能够整除a，且能整除b。
最大公约数即，最大的约数。若设其为d，则有c能整除d。
其大概原理是：
a,b两数，若a>=b，则存在唯一的a=q*b+r；（0<=r<b）
同理：
b=q1*r+r1；（0<=r1<r）
r=q2*r1+r2；（0<=r2<r1）
r1=q3*r2+r3；（0<=r1<r）
如此以往，则一定有 ：
r（n-2）=qn*r（n-1）+rn；（rn=0）
此时qn则为最大公约数。
具体原理可以见附录。我也是靠那个看懂的。
核心步骤为：
while (b!=0)
{
c=a;
a=b;
b=c%b;
}
此时，a为最大公约数。
5、第四步：求最小公倍数
有了最大公约数，最小公倍数就顺势而出，即两数相乘再除以最大公约数。
为了保留原始数据，可以在开始时加设两个变量。
核心步骤为：
x=a;
y=b;
……
求出最大公约数，并赋值于a后：
c=x*y/a;
6、最终完整程序为：
# include<stdio.h>
int main()
{
int a,b,c,x,y;
printf("请输入两个正整数，用逗号间隔：");
scanf("%d,%d",&a,&b);
x=a;
y=b;
if (a<b)
{
c=a;
a=b;
b=c;
}
while (b!=0)
{
c=a;
a=b;
b=c%b;
}
c=x*y/a;
printf("最大公约数为%d,最小公倍数为%d",a,c);
return 0;
}
