javascript - 如何在 Javascript 中计算自然数 1 到 N 的 LCM？

Question

所以，我的问题是找到能将 1 到 20 的所有数字均分的最小倍数。我确实成功地解决了这个任务，但我的程序运行得相当慢。这是代码，我使用的最终数字是 1 亿。可以想象，这会花费很多时间。所以我想知道，我将如何优化这段代码？此外，如果知道如何更改应划分的数字个数会很好，所以我们将 1 到 20 改为 1 到 15。

function smallestMultiple(n) {
    for (i = 0; i< n; i++) {
        if (i%1 === 0 && i%2 === 0 && i%3 === 0 && i%4 === 0 && i%5 === 0 
                 && i%6 === 0 && i%7 === 0 && i%8 === 0 && i%9 === 0 
                 && i%10 === 0 && i%11 === 0 && i%12 === 0 && i%13 === 0 
                 && i%14 === 0 && i%15 === 0 && i%16 === 0 && i%17 === 0 
                 && i%18 === 0 && i%19 === 0 && i%20 === 0 ) {

            console.log(i);
        }
    };
};

很明显，这花了 5 分钟多才找到答案。我想知道是否有更有效的方法？编辑:显然我也可以使用 1-20 的变量。将对此进行调查，如果您有答案，请彻底解释您的答案以及为什么它更有效。

Answer 1

我想我找到了最优雅的解决方案之一，直接来自论坛:

Without actually trying it, I imagine that a few of the "brute force" methods here violate the "1 minute rule". However, considering a minor change can greatly improve the efficiency of the algorithm.

The "brute force" approach is assumed to be: iterate over each natural number - if the current is evenly divisible by each of the numbers 1 through 20, you've found your answer.

Consider this: if you know that the solution for N is X, then the solution for N+1 must be divisible by X. Therefore, when iterating through the natural numbers, you can iterate by X instead of 1. And instead of checking for the divisibility of the numbers 1 to N+1, you only have to check for N+1, since you already know that the values (multiples of X) are all divisible by 1 to N.

As an example, given that the answer for 10 is 2520, to get the solution of 11, we check if 2520 is evenly divisible by 11. It isn't, we iterate to 5040 and check if that is divisible by 11. We continue until we discover that 27720 is divisible by 11, which is out answer.

Despite making no attempt to directly determine LCDs, this ends up being a fairly speedy algorithm, running easily under a second for somewhat larger values of N.

In Ruby (though a similar approach can be used in many high-level languages):

def snd(max) result = 1 for n in 1..max prev = result while result % n > 0 result += prev end end return result end

puts snd(20)

然后我将其解释为 Javascript 并得到了这个脚本

console.log("Please type in smallestMultiple(n), whereas n is the smallest multiple.");

function smallestMultiple(n) {
   var result = 1;
   var prev;
   for (i=1; i<n+1; i++) {
       prev = result;
       while (result%i > 0) {
           result += prev;
       }
   }
   console.log(result);
};

<script src="https://getfirebug.com/firebug-lite-debug.js"></script>

编辑:在将返回 smallestNumber(11) = 2520 的脚本中发现错误。在 for 循环中修复:for(i=0; i<< strong>n+1;i++)