c

语⾔最⼤公约数最⼩公倍数的编程

,C

语⾔三种算法求解最⼤

公约数与最⼩公倍数

...

C语⾔三种算法求解最⼤公约数与最⼩公倍数

最⼤公约数与最⼩公倍数的求解是很多初学C的⼈所⾯临的⼀道问题。当然这道问题并不难解答，也有很多⼈已经写过相关的博客，我在此

书写此篇博客，⼀是为了让⾃⼰能够夯实基础，另外就是希望能够帮到和我⼀样的初学者。

当然，在写这篇博客之前，我已经做过相关资料的调查，可能读者会发现此篇博客会与其他⼈的博客有所重复，但是，我保证绝未抄袭。好

了，进⼊正题！

问题：请从键盘上输⼊两个数值 x，y，请⽤C语⾔求出这两个数值的最⼤公约数与最⼩公倍数。

⾸先，我们要想解决这道问题，就要了解什么是最⼤公约数与最⼩公倍数。

最⼤公因数；也称最⼤公约数、最⼤公因⼦，指两个或多个整数共有约数中最⼤的⼀个。----来源百度百科

最⼩公倍数：两个或多个整数公有的倍数叫做它们的公倍数。----来源百度百科

了解了其含义，接下来就是构思算法，通常⽽⾔，求解最⼤公约数有三种算法，⽽最⼩公倍数的求解，我们可以很容易的推断出，最⼩公倍

数等于两个数值的乘积除以这两个数值的最⼤公约数。那么接下来的算法我将在此⼀⼀进⾏列举和解释。

1.辗转相除法：

⼜名欧⼏⾥德算法(Euclidean algorithm)，它是已知最古⽼的算法， 其可追溯⾄公元前300年前。 ----来源百度百科

辗转：望⽂⽣义，就是翻来覆去。相除就很好理解了，就是进⾏除法运算。

辗转相除法的核⼼就是不断的让两个数做除法运算。其原理基于两个整数的最⼤公约数等于其中较⼩的数和两数的相除余数的最⼤公约数。

假设两数为 x，y。

先令 z = x % y ;

之后 y 赋给 x 即令  x = y ;

再将 z 赋给 y 即令  y = z；

辗转相减，其终⽌条件为：y 等于0时。

代码如下：

#include

int main()

{

int x, y, z, m, n;

printf("请输⼊两个数：");

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

m = x, n = y;

while (y != 0)

{

z = x%y;

x = y;