一、求最大公约数:欧几里德算法
欧几里德算法又称辗转相除法用于计算两个正整数a,b的最大公约数
其计算原理依赖于下面的定理:
定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数最大公约数缩写为gcd。
//两个数的最大公约数--欧几里德算法
//总是将较小的数放在b中
在已经算絀整数a、b的最大公约数的基础上我们可以通过下面的公式来求出它们的最小公倍数算法
//求a、b的最小公倍数算法
三、求n个数的最大公约数
思路:把n个数保存为一个数组,参数为数组的指针和数组的大小(需要计算的数的个数)然后先求出gcd(a[0], a[1]),然后将所求的gcd与数组的下一個元素作为gcd的参数继续求gcd这样就产生一个递归的求ngcd的算法
四、求n个数的最小公倍数算法
思路:算法过程和n个数的最大公约数求法类似,求出头两个的最小公倍数算法再讲其和下一个元素求最小公倍数算法直到数组末尾,这样就产生一个地柜的求nlcm的算法