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

Question

所以,我的问题是找到从1到20均匀分配到所有数字的最小倍数.我确实成功地解决了这个任务,但我的程序运行得相当慢.这是代码,ni使用的最终数字是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

我想我发现了一个最优雅的解决方案,直接来自论坛:

在没有真正尝试的情况下,我想这里的一些"蛮力"方法违反了"1分钟规则".但是,考虑到微小的改变可以大大提高算法的效率.

假设"强力"方法是:迭代每个自然数 - 如果当前数字可以被1到20中的每个数字整除,你就找到了答案.

考虑一下:如果你知道N的解是X,那么N + 1的解必须可以被X整除.因此,当迭代自然数时,你可以迭代X而不是1.而不是检查数字1到N + 1的可分性,你只需要检查N + 1,因为你已经知道值(X的倍数)都可以被1到N整除.

作为一个例子,假设10的答案是2520,为了得到11的解,我们检查2520是否可被11整除.不是,我们迭代到5040并检查它是否可被11整除.我们继续直到我们发现27720可以被11整除,这就是答案.

尽管没有尝试直接确定LCD,但这最终成为一种相当快速的算法,在较小的N值下,在一秒钟内容易运行.

在Ruby中(虽然类似的方法可以在许多高级语言中使用):

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

放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 < n + 1 ; i ++)