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 に答える