C语言 辗转相除法求最大公约数和最小公倍数

C语言 辗转相除法求最大公约数和最小公倍数

网上有一些只能求出最小公约数的“最大公约数求法”经验，我也是醉了。同样作为初学，在认真阅读了求最大公约数的求法原理——辗转相除法后，分享一下我的经验。

总述：求最大公约数和最小公倍数可以分为四步，先罗列出一些关键步骤。

第一步：输入数据

核心步骤为：

printf("请输入两个正整数，用逗号间隔：");

scanf("%d,%d",&x,&y);

第二步：比较大小

由于辗转相除是不断通过余数来作为除数的，所以刚输入的数据，一定是大除以小。为了保证数据的严密，需要比较调整一下两数大小。

核心步骤为：

if (a

{

c=a;

a=b;

b=c;

}

保证了a>=b。

第三步：辗转相除求最大公约数

虽然辗转相除法是C语言的入门，但是我觉得其数学理论还是需要看的。这样才不会死记硬背，才能理解。只有准确理解了最大公约数的概念，才不会编出一个求出最小公约数的程序。

约数的概念为：

一对正整数a，b；存在c，能够整除a，且能整除b。

最大公约数即，最大的约数。若设其为d，则有c能整除d。

其大概原理是：

a,b两数，若a>=b，则存在唯一的a=q*b+r；（0<=r

同理：

b=q1*r+r1；（0<=r1

r=q2*r1+r2；（0<=r2

r1=q3*r2+r3；（0<=r1

如此以往，则一定有 ：

r（n-2）=qn*r（n-1）+rn；（rn=0）

此时qn则为最大公约数。

具体原理可以见附录。我也是靠那个看懂的。

核心步骤为：

while (b!=0)

{

c=a;

a=b;

b=c%b;

}

此时，a为最大公约数。

第四步：求最小公倍数

有了最大公约数，最小公倍数就顺势而出，即两数相乘再除以最大公约数。

为了保留原始数据，可以在开始时加设两个变量。

核心步骤为：

x=a;

y=b;

……

求出最大公约数，并赋值于a后：

c=x*y/a;

最终完整程序为：

# include

int main()

{

int a,b,c,x,y;

printf("请输入两个正整数，用逗号间隔：");

scanf("%d,%d",&a,&b);

x=a;

y=b;

if (a

{

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;

}