求最大公约数的简便方法

Question

如题所述

Answer 1

求最大公约数的简便方法如下：

1、辗转相除法（欧几里德法）C语言中用于计算两个正整数a，b的最大公约数，采用函数嵌套调用形式进行求两个数的最大公约数。其算法过程为：

前提：设两数为a，b设其中a做被除数，b做除数，temp为余数；Steps：大数放a中，小数放b中；求a/b的余数；若temp=0则b为最大公约数。如果temp！=0则把b的值给a,temp的值给a。

2、穷举法（枚举法）

从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。

3、更相减损法

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

以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

4、Stein算法

性质：gcd（kx，ky）=k*gcd（x，y）。

对两个正整数 x>y。

均为偶数gcd（x，y）=2gcd（x/2，y/2）。

均为奇数gcd（x，y）=gcd（（x+y）/2，（x-y）/2）。

X奇y偶gcd（x，y）=gcd（x-y）/2）。

X偶y奇gcd（x，y）=gcd（x/2，y）。

或gcd（x，y）=gcd（y，x/2）。