【算法】Smallest Common Multiple -- 求最小公倍数

30
从题目开始吧:
题目是这个样子的:

找出能被两个给定参数和它们之间的连续数字整除的最小公倍数。

范围是两个数字构成的数组,两个数字不一定按数字顺序排序。

例如对 1 和 3 —— 找出能被 1 和 3 和它们之间所有数字整除的最小公倍数。

解法

(捂脸)这明明是个数学题好吗( ▼-▼ )!!!

几个数共有的倍数叫做这几个数的公倍数,其中除0以外最小的一个公倍数,叫做这几个数的最小公倍数。

可以用公式法求得两个数的最小公倍数:

假设有自然数 a 、b,则:

a、b最小公倍数 * a、b最大公约数 = a、b的乘积

那么重点就是求 a 、 b的最大公约数了。

什么? 你不会求最大公约数? 没事没事,我也不会。。。

但是没关系啊,伟大的先人欧几里得会:

这里使用欧几里得算法,也可以叫做是辗转相除法:

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为252 − 105 = 21 × (12 − 5) = 147,所以147和105的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21 = 5 × 105 + (−2) × 252。这个重要的结论叫做裴蜀定理。
辗转相除法原理图解

证明方法的话可以看这里

1
gcd(a,b) = gcd(b,a mod b)

其中,a mod b表示 a ÷ b 的余数,它的值不为 0。

该定理可以被这样证明:

a可以表示成a = kb + r(a,b,k,r皆为正整数),则r = a mod b

假设d是a,b的一个公约数,记作d|a,d|b,即a和b都可以被d整除。

而r = a - kb,两边同时除以d,r/d=a/d-kb/d=m,等式左边可知m为整数,因此d|r

因此d也是(b,a mod b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。
由此可得我们计算两个数最大公约数的函数表达式:

1
2
3
4
5
6
var gcd = function(a,b){
if(b){
return gcd(b, a % b);
}
return a;
};

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function smallestCommons(arr) {
var strs = [];
if (arr[0] > arr[1]){
for (var i = arr[1]; i <= arr[0]; i++) {
strs.push(i);
}
}else {
for (var m = arr[0]; m <= arr[1]; m++) {
strs.push(m);
}
}
var gcd = function(a,b){
if(b){
return gcd(b, a % b);
}
return a;
};

return strs.reduce(function(prev,cur,index,array){
return prev*cur/gcd(prev,cur);
});

}