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

How to calculate LCM for natural numbers 1 to N in Javascript?

本文关键字：LCM 自然数 计算 Javascript      更新时间：2023-09-26

所以，我的问题是找到能平均除以从1到20的所有数字的最小倍数。我确实成功地解决了这个任务，但是我的程序运行得很慢。这是代码，我用的n的最终数字是1亿。你可以想象，这需要很多时间。我想知道，如何优化这段代码?此外，如果知道如何改变它应该分成的数字的数量就好了，所以我们说1到15，而不是1到20。

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的变量。我会调查的，如果你有答案，请详细解释你的答案，以及为什么它更有效率。

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

在没有实际尝试的情况下，我想象一些"蛮力"这里的方法违反了"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中(尽管类似的方法可以用于许多高级语言):

defsnd (max) result = 1 for n in 1Prev = result结果% n> 0Result += prevEnd返回结果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<<strong> n + 1 ,我+ +)

用最大公约数约法

跳过数字1 - 10，因为你可以把它们中的任何一个乘以2，得到列表中的另一个因子。

function GCF(a, b) {
    if (b == 0) return a;
    else return (GCF (b, a % b));
}
function LCM(a, b) {
    return Math.abs(a*b) / GCF(a, b);
}
LCM(11, LCM(12, LCM(13, LCM(14, LCM(15, LCM(16, LCM(17, LCM(18, LCM(19, 20)))))))));

对于任意n，不是超级优化，但很简单，就像:

function LCM_N(n) {
    var x = 1;
    while (n > 1) {
        x = LCM(n, x);
        n--;
    }
    return x;
}

你想要的是1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20

这与20、19、18、17、16、15、14、13、12、11的最小公倍数(LCM)相同，因为1、2、3、4、5、6、7、8、9、10都是其他10个数的因数。

你应该使用while循环，因为它们更快。

LCM必须小于或等于20、19、18、17、16、15、14、13、12、11的倍数，这样n才可以从这个倍数开始。

i可以从数列中所有质数的倍数开始:19*17*13*11*7*5*3*2

break退出循环。这可能就是为什么你花了这么长时间。

我们可以加20，因为这是两个答案之间可能的最小差异。

function lowestCommonMultipleof20Through1(){
  var i = 19*17*13*11*7*5*4*3; 
  var n = 20*19*18*17*16*15*14*13*12*11;
  while(i < n){
    if( 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);
      break;
    }
    i+=20;
  }
}

我几乎立刻得到了232792560。

相关文章：