用欧几里得迭代算法求两个数的最小公倍数

Question

如题所述

Answer 1

用欧几里得算法算125和71的最小公倍数：

设为a,b,

先求出最大公约数gcd(a,b)  再用  lcm(a,b)= a*b/ gcd(a,b); 

最大公约数用这个递归算法

对应过程 

gcd(125,71) =  gcd(71, 125%71) = gcd(71,54) =gcd(54,71%54) = gcd(54,17) 

=gcd(17,54%17)= gcd(17,3) =gcd(3,17%3) =gcd(3,2) =gcd(2,3%2) = gcd(2,1) = gcd(1,2%1) =gcd(1,0)

所以最大公约数gcd(125,71)= 1;   最小公倍数  lcm=125*71=8875

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

辗转相除法的算法步骤为，两个数中用较大数除以较小数，再用出现的余数除除数。

再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

辗转相除法是利用以下性质来确定两个正整数a和b的最大公因子的：

1、若r是a ÷ b的余数，且r不为0，则gcd(a,b) = gcd(b,r)。

⒉、a和其倍数之最大公因子为a。

另一种写法是：

⒈、令r为a/b所得余数（0≤r），若r= 0，算法结束；b即为答案。

⒉、互换：置a←b，b←r，并返回第一步。