问题
2520是一个能被1到10整除的最小正整数。
求能被1到20整除的最小正整数。
* 传送门
分析
显然是一个求最小公倍数（Least Common Multiple，LCM）的问题，这里最有趣的地方是拿出两个数字算出最小公倍数后，需要继续使用这个最小公倍数与后面的数字陆续产生一个新的最小公倍数，不断循环。
要获得最小公倍数的计算方法，首先要搞清楚最大公约数（Greatest Common Divisor，GCD）的定义，因为求两数字a和b最小公倍数，就是将两数相乘然后除以它们的最大公约数：
\(
LCM(a, b) = \frac{a \times b}{GCD(a, b)}
\)
而最大公约数的运算核心就是要求余，通过递归的方式不断求余，当发现余数为0时，非0的那个数字就是最大公约数：
\(
GCD(a, b) =
\begin{cases}
a,& \text{if } b = 0\\
GCD(b, a \mod b)
\end{cases}
\)
答案
由于最大公约数的定义自身就是尾递归，所以直接转换成代码就可以：
// answer: using lcm
const start = Date.now()
function gcd(a, b) {
if (b == 0) return a
else return gcd(b, a % b)
}
const lcm = (a, b) => a * b / gcd(a, b)
var result = 1
for (let i = 2; i <= 20; ++i)
result = lcm(result, i)
// 不嫌浪费内存的话，可以创造一个1到20的数组然执行reduce
// result = Array.apply(null, { length: 20 }).map((v,i) => i + 1, Number).reduce(lcm)
alert(result + ', ' + (Date.now() - start) + 'ms')
由 bruce 于 2020-06-8 19:07 更新
