javascript - 欧拉计划 #5 效率和错误

Question

来自网站的问题:

2520 是可以被 1 到 10 中的每个数字整除而没有余数的最小数字。

能被 1 到 20 中所有数字整除的最小正数是多少？

<小时/>

我的问题

我有一个问题，涉及代码中的效率和错误。当我无法通过自己的方式通过时，我研究并查看了其他答案，但我仍然不明白这是如何实现的。另外，当我将代码插入 1-10 的 2520 时，我的代码显然无法工作。

请注意，我不想要有关效率的答案或解决方案，只是解释我如何实现它(又名提示)。但对于我的代码中的错误，我想要一个解决方案。预先感谢您的帮助!

var recentArray = [];
var fullArray = [];
var numberCheck = 20;

function makeNewNumbers(i1, i2) {

    for (var i = i1; i < i2; i++) {
        recentArray = [];
        for (var j = 2; j <= numberCheck; j++) {
            recentArray.push(i % j);
        }
        fullArray.push(recentArray);
    }
}

var counter = 0;
var iStart = 0,
    iLess = 1000;
var success = false;

var newCheck = setInterval(function () {
    while (counter < 10 && success === false) {
        counter++;
        makeNewNumbers(iStart, iLess);
        for (var o = 1; o < fullArray.length; o++) {
            recentFound = false;
            if (numberCheck === 20 && fullArray[o][0] === 0 && fullArray[o][1] === 0 && fullArray[o][2] === 0 && fullArray[o][3] === 0 && fullArray[o][4] === 0 && fullArray[o][5] === 0 && fullArray[o][6] === 0 && fullArray[o][7] === 0 && fullArray[o][8] === 0 && fullArray[o][9] === 0 && fullArray[o][10] === 0 && fullArray[o][11] === 0 && fullArray[o][12] === 0 && fullArray[o][13] === 0 && fullArray[o][14] === 0 && fullArray[o][15] === 0 && fullArray[o][16] === 0 && fullArray[o][17] === 0 && fullArray[o][18] === 0) {
                clearInterval(newCheck);
                console.log("Success!!! Number: " + o);
                success = true;
                break;
            } else if (numberCheck === 10 && fullArray[o][0] === 0 && fullArray[o][1] === 0 && fullArray[o][2] === 0 && fullArray[o][3] === 0 && fullArray[o][4] === 0 && fullArray[o][5] === 0 && fullArray[o][6] === 0 && fullArray[o][7] === 0 && fullArray[o][8] === 0) {
                clearInterval(newCheck);
                console.log("Success!!! Number: " + o);
                success = true;
                break;
            }
        }
    }
    iStart += 1000;
    iLess += 1000;
    console.log("Not found...\nSearch is continued. To postpone type \'clearInterval(newCheck)\'\nNerd stats: --- Starting minimum: " + iStart + " --- Starting maximum: " + iLess);
}, 1);

Answer 1

使用数学，而不是暴力。

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

从数学上讲，这称为 least common multiple共 1, ..., 20 个。

计算两个数字的最小公倍数的一种非常快速的方法是使用 Euclidean algorithm计算 greatest common divisor .

function gcd(a, b) { // Greatest common divisor
  if(b == 0) return a;
  return gcd(b, a%b);
}
function lcm(a, b) { // Least common multiple
  return a * b / gcd(a, b);
}
var n = 1;
for(var i=1; i<=20; ++i) n = lcm(n, i);
n; // 232792560