项目Euler #5 -最小倍数

Question

JavaScript是我的第一种编程语言，我还是很新的。我只是在寻求反馈。我能做些什么来提高效率和处理更大的数字呢？

// Project Euler - Smallest Multiple
// This program finds the smallest positive number
// that is evenly divisible by all numbers between 1 and n.

function smallestMult(n){
    var dividends = []; // the numbers by which the program must divide
    for (var i = 1; i <= n; i ++){
        dividends.push(i);
    }
    var result = n; // will increase in increments of n
    var count = 0; //  result has been found when count == n
    while (count < n){
        for (var x = 0; x < dividends.length; x ++){
            if (result % dividends[x] === 0){
                count += 1; // increases count for every successful division
            }
            else {
                count = 0; // if a division fails, count returns to 0
                result += n; // and the result is increased by n
            }
        }
    }
    return result;
}
console.log(smallestMult(12));

Answer 1

换句话说，“最小倍数”是一系列数字中最不常见的倍数。下面的函数实现了最不常见的多个lcm：

var lcm = function (a, b) {
    // lcm is defined as:
    // lcm(a, b) = abs(a * b) / gcd(a, b)
    if (isNumber(a) && isNumber(b)) {
        if (!isInteger(a) || !isInteger(b)) {
            throw new Error('Parameters in function lcm must be integer numbers');
        }
        return (Math.abs(a) / gcd(a, b)) * Math.abs(b);
    }
};

辅助函数isNumber和isInteger如下：

var isNumber = function(value) {
    return (value instanceof Number) || (typeof value == 'number');
};

var isInteger = function(value) {
  return (value === Math.round(value));
};

现在我们必须实现gcd，这是最大的公共除数。在这里，我们可以使用欧氏算法：

var gcd = function (a, b) {
    if (isNumber(a) && isNumber(b)) {
        if (!isInteger(a) || !isInteger(b)) {
            throw new Error('Parameters in function gcd must be integer numbers');
        }

        // http://en.wikipedia.org/wiki/Euclidean_algorithm
        while (b != 0) {
          r = a % b;
          a = b;
          b = r;
        }
        return (a < 0) ? -a : a;
    }
};

现在我们有了lcm，我们将使用lcm(a,b,c)≡lcm(lcm(a,b),c)来创建smallestMultiple函数：

var smallestMultiple = function (endOfRange) {
    if (isNumber(endOfRange)) {
        if (endOfRange <= 0) {
            throw new Error('Parameter in function smallestMultiple must be greater than zero');
        }
        if (!isInteger(endOfRange)) {
            throw new Error('Parameter in function smallestMultiple must be a positive integer');
        }
        // Observing that lcm(a,b,c) ≡ lcm(lcm(a,b),c)
        var a = 1;
        for (var i = 1; i <= endOfRange; i++) {
            a = lcm(a, i);
        }
        return a;
    }
};

完整的代码如下：

var isNumber = function(value) {
    return (value instanceof Number) || (typeof value == 'number');
};

var isInteger = function(value) {
  return (value === Math.round(value));
};

var gcd = function (a, b) {
    if (isNumber(a) && isNumber(b)) {
        if (!isInteger(a) || !isInteger(b)) {
            throw new Error('Parameters in function gcd must be integer numbers');
        }

        // http://en.wikipedia.org/wiki/Euclidean_algorithm
        while (b != 0) {
          r = a % b;
          a = b;
          b = r;
        }
        return (a < 0) ? -a : a;
    }
};

var lcm = function (a, b) {
    // lcm is defined as:
    // lcm(a, b) = abs(a * b) / gcd(a, b)
    if (isNumber(a) && isNumber(b)) {
        if (!isInteger(a) || !isInteger(b)) {
            throw new Error('Parameters in function lcm must be integer numbers');
        }
        return (Math.abs(a) / gcd(a, b)) * Math.abs(b);
    }
};

var smallestMultiple = function (endOfRange) {
    if (isNumber(endOfRange)) {
        if (endOfRange <= 0) {
            throw new Error('Parameter in function smallestMultiple must be greater than zero');
        }
        if (!isInteger(endOfRange)) {
            throw new Error('Parameter in function smallestMultiple must be a positive integer');
        }
        // Observing that lcm(a,b,c) ≡ lcm(lcm(a,b),c)
        var a = 1;
        for (var i = 1; i <= endOfRange; i++) {
            a = lcm(a, i);
        }
        return a;
    }
};

上面所有内容的要点不是要告诉您如何处理更大的数字的效率，而是关于一些更重要的事情，特别是对于像您和我这样的初学者：抽象。

抽象意味着给事物起名字，所以你可以把它们称为一个单位。例如，“搅拌”、“炒”和“煮沸”是抽象的。哪一个更好：“搅拌10分钟，煎牛排，烧开水”还是“把勺子往锅里移10分钟，在冰箱上加热一点油，然后把牛排放在上面，然后把水调到100摄氏度的温度”。请注意，前者的描述性更强，尽管不那么详细。类似地，将smallestMultiple定义为一系列数字的lcm比特殊过程更有帮助。当你得到一份程序员的工作时，请记住抽象是最重要的，并且是过早的优化是万恶之源。。

另外，如果验证过度或不明确，很抱歉，因为javascript不是我的主要语言，而且它的动态和弱分型相结合使我有点害怕它。