c语言求最大公约数多一个负号,C语言 求最大公约数

质因数分解法

质因数分解 质因数分解法：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的

最大公约数。

例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，(24、60)=12。

把几个数先分别分解质因数，再把各数中的全部公有的质因数和独有的质因数提取出来连乘，所得的积就是这几个数的

最小公倍数。

例如：求6和15的 最小公倍数。先分解质因数，得6=2×3，15=3×5，6和15的全部公有的质因数是3，6独有质因数是2，15独有的质因数是5，2×3×5=30，30里面包含6的全部质因数2和3，还包含了15的全部质因数3和5，且30是6和15的公倍数中最小的一个，所以[6，15]=30。

短除法

短除法：短除法求最大公约数，先用这几个数的公约数连续去除，一直除到所有的商互质为止，然

后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。

短除法求最小公倍数，先用这几个数的公约数去除每个数，再用部分数的公约数去除，并把不能整除的数移下来，一直除到所有的商中每两个数都是 互质的为止，然后把所有的除数和商连乘起来，所得的积就是这几个数的最小公倍数，例如，求12、15、18的最小公倍数。

短除法的格式 短除法的本质就是质因数分解法，只是将质因数分解用短除符号来进行。

短除符号就是除号倒过来。短除就是在除法中写 除数的地方写两个数共有的 质因数，然后落下两个数被公有质因数整除的商，之后再除，以此类推，直到结果 互质为止(两个数互质)。

而在用短除计算多个数时，对其中任意两个数存在的因数都要算出，其它没有这个 因数的数则原样落下。直到剩下每两个都是互质关系。

求最大公因数便乘一边，求最小公倍数便乘一圈。

无论是短除法，还是分解质因数法，在质因数较大时，都会觉得困难。这时就需要用新的方法。

辗转相除法

古希腊数学家欧几里德 辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫 欧几里德算法。

这就是辗转相除法的原理。

辗转相除法的格式 例如，求(319，377)：

∵ 319÷377=0(余319)

∴(319，377)=(377，319)；

∵ 377÷319=1(余58)

∴(377，319)=(319，58)；

∵ 319÷58=5(余29)，

∴ (319，58)=(58，29)；

∵ 58÷29=2(余0)，

∴ (58，29)= 29；

∴ (319，377)=29.

可以写成右边的格式。

用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。

更相减损法

刘徽《九章算术》 更相减损法：也叫 更相减损术，是出自《 九章算术》的一种求最大公约数的算法，它原本是为 约分而设计的，但它适用于任何需要求最大公约数的场合。

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫

等值算法。

例1、用更相减损术求98与63的最大公约数。

解：由于63不是偶数，把98和63以大数减小数，并辗转相减：

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98和63的最大公约数等于7。

这个过程可以简单的写为：

(98，63)=(35，63)=(35，28)=(7，28)=(7，21)=(7，14)=(7，7)=7.

例2、用更相减损术求260和104的最大公约数。

解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。

此时65是奇数而26不是奇数，故把65和26辗转相减：

65-26=39

39-26=13

26-13=13

所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。

这个过程可以简单地写为：

(260,104)=(65,26)=(39,26)=(13,26)=(13,13)=13.

[1]

比较辗转相除法与更相减损术的区别

(1)都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

[2-3]

常用结论

编辑

在解有关最大公约数、最小公倍数的问题时，常用到以下结论：

(1)如果两个自然数是互质数，那么它们的最大公约数是1，最小公倍数是这两个数的乘积。

例如8和9，它们是互质数，所以(8，9)=1，[8，9]=72。

(2)如果两个自然数中，较大数是较小数的倍数，那么较小数就是这两个数的最大公约数，较大数就是这两个数的最小公倍数。

例如18与3，18÷3=6，所以(18，3)=3，[18，3]=18。

(3)两个整数分别除以它们的最大公约数，所得的商是互质数。

例如8和14分别除以它们的最大公约数2，所得的商分别为4和7，那么4和7是互质数。

(4)两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。

例如12和16，(12，16)=4，[12，16]=48，有4×48=12×16，即(12，16)× [12，16]=12×16。

(5)GCD(a,b) is the smallest positive linear combination of a and b. a与b的最大公约数是最小的a与b的正线性组合,即对于方程xa+yb=c来说,若x,a,y,b都为整数,那么c的最小正根为gcd(a,b).