0

我试图遍历一个很大的数字（准确地说是 60 亿），但我不能，因为我的电脑死机了。我该如何解决这个问题。我应该找到 的最大素因数600851475143。

function prime(n) {
    if (n === 1 || n === 2) return false;
    if (n % 2 === 0 || n % 3 === 0) return false;
    return true;
}
var n = 600851475143;
for (var i = 1, c = []; i < n; i++) {
    if ((n % i === 0) && prime(i)) {
        c.push(i);
    }
}

我已经完成了。我将素数存储在一个数组中。

4

2 回答 2

2

您的prime()功能没有按照名称所说的那样做。有许多有效的分解素数的方法，例如，试试这个：

var x = 600851475143;
var i = 2;
var sk;
while(i <= x) 
{
    while (x % i == 0)
    {
        sk = i;
        x = x / i;
    }
    i++;
}
console.log(sk);

输出：6857

此页面有另一个（查看源代码）功能用于分解。

于 2012-06-07T23:31:58.057 回答
1

该prime函数不仅返回素数，还返回所有非 1 或不能被 2 和 3 整除的正整数。

让我们再看看整个算法。首先，请注意您不需要遍历n，您可以停在它的平方根处（考虑一下）。

var divs = [];
if (!(n & 1)) { // Checking if n is even, using faster bit operators
    divs.push(2);
    while (!(n & 1)) n >>= 1;
}
var d = 3, l = Math.sqrt(n);
while (d < l) {
    if (!(n % d)) {
        divs.push(d);
        while (!(n % d)) n /= d;
        l = Math.sqrt(n);
    }
    d += 2; // No even numbers except 2 are prime, so we skip them
}
if (n !== 1) divs.push(n);

现在divs[divs.length - 1]包含 的最大素除数n和divs所有素因数。

于 2012-06-07T23:54:35.863 回答