原理
最大公约数
两个数的最大公约数可以用辗转相除法.
辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252和105的最大公约数是21( 252 = 21 × 12;105 = 21 × 5 );因为 252 − 105 = 21 × (12 − 5) = 147 ,所以147和105的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数就是两数的最大公约数。
最小公倍数
两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。
例如12和16,(12,16)=4,[12,16]=48,有4×48=12×16,即(12,16)× [12,16]=12×16。
代码
//最大公约数
function gys(x, y) {
var max, min, temp;
max = x > y ? x : y;
min = x < y ? x : y;
if(x == 0 || y == 0){
return max;
}
while (max % min) {
temp = max % min;
max = min;
min = temp;
}
return min;
}
//最小公倍数
function gbs(x, y) {
return x * y / gys(x, y);
}
console.log('最大公约数:' + gys(252, 105))//最大公约数:21
console.log('最小公倍数:' + gbs(252, 105))//最小公倍数:1260
//最大公约数的递归算法
function gys2(m, n) {
return m % n == 0 ? (n) : (gys2(n, m % n));
}
//数组的最小公倍数
function arrGbs(arr){
var midNum = 1;
for(var i = 0;i < arr.length;i++){
midNum = gbs(arr[i],midNum);
}
return midNum;
}
console.log(arrGbs([2,3,7,16]))//336