javascript - 使用 JavaScript 检查质数

Question

我现在正在做第三个项目欧拉问题。到目前为止，我已经想出如何解决找到 600851475143 的最大质因数的问题。

我写了一小段代码，可以将一个数的所有质因数放入一个数组中。我遇到的问题是数字可能太大而无法计算。我使用了其他大数字(没有这个大)，它们工作正常，但这个只是卡住页面，就像它处于无限循环中一样。这是代码:

var primes = [];
function factor (largestNumber) {
    var a = largestNumber;
    var b = 2; 
    while (b < largestNumber) {
        if (a % b == 0) {
            a /= b;
            primes.push(b);
            b = 2;

        } else {
            b++;
        }
    }
}

factor(600851475143);
console.log(primes);

Answer 1

你的算法不是最优的。

function factor(largestNumber) {
    var primes = [];                          // using local value
    var a = largestNumber;
    var b = 2;
    while (b <= Math.floor(Math.sqrt(a))) {   // we do not need to check whole number
                                              // over and over again.
                                              // We could check to a only 
                                              // or even to sqrt(a) only
        if (a % b == 0) {
            a /= b;
            primes.push(b);
                                             // there is no reason to reset value
        } else {
            b++;
        }
    }
    primes.push(a);                          // rest number would be always prime
    return primes;
}

console.log(factor(600851475143));