1

http://projecteuler.netから javascript を使用して数学的な問題を解決しようとしてい ます: 200 万未満のすべての素数の合計を見つけます。私が書いたスクリプトを実行すると、ブラウザーがクラッシュします (私は Google Chrome を使用しています)。これはスクリプトです：

function isPrime(num) 
{ 
    if(num < 2) 
    return false; 
    for (var i = 2; i < num; i++) 
        { 
        if(num%i==0) 
        return false; 
        } 
return true; 
} 
var total=0e1;
    for (var i = 1; i < 2000000; i++)
        { 
        if(isPrime(i)) 
            {
            total=total+i;
            }
        } 

document.write("The sum of all the primes below two million is ",total);

スクリプトは、小さい数値 (i<100000) に対しては正常に機能します。それの何が問題なのですか？どうすれば修正できますか？ご協力いただきありがとうございます。

4

2 に答える 2

1

この関数は、チェックするnごとにnisPrimeモジュロ演算を実行します (因数として素数より小さいすべての数値をチェックするため)。約 7 分の 1 の数が素数であると仮定すると、スニペットで関数を約 28,000 回実行し、モジュロ演算を約 3 億 9,200 万回実行することになります。JavaScript エンジンが無限ループに入ったと想定しているため、Chrome がクラッシュしている可能性があります。isPrime

NullUserException が言ったように、素数を見つけるより良い方法があります。

単純な改善は、平方根より小さい数値の因数のみをチェックすることです。a = b * cである任意の数値aについて、 bまたはcのいずれかがaの平方根より小さいと仮定できます。ある数が素数でないことを知るには 1 つの因数だけを知る必要があるため、その平方根より小さい因数を探すだけで済みます。lanzz がコメントしたように、偶数をスキップすることもできます。

function isPrime(n)
{
    if (n % 2) return false;       

    var s = Math.sqrt(n);

    // iterate by 2 to skip even numbers
    for (var i = 3; i <= s; i += 2)
        if (n % i) return false;

    return true;
}

var total = 3; // 1 + 2

// iterate by 2 to skip even numbers
for (var i = 3; i < 2000000; i += 2)
    if (isPrime(i)) total += i;

誤解しないでください。これはアルゴリズムのOの複雑さを変えることはなく、十分な数で JavaScript エンジンをクラッシュさせることになります。しかし、それはクラッシュする数を増やします。200万まで使えるかどうかはわかりません。

于 2012-10-24T21:45:30.643 に答える
0

この関数を試してみてください。あなたのアルゴリズムよりもはるかに高速なアルゴリズムを使用しており、2M の数値でクラッシュすることはありません。

function isPrime( num ) {
    var testNum = 3;
    var limitNum = num;

    if ( num == 2 )
        return true;

    if ( num % 2 == 0 )
        return false;

    while ( limitNum > testNum ) {
        if ( num % testNum == 0 ) {
            return false;
        }

        limitNum = parseInt( num / testNum );
        testNum += 2;
    }

    return true;
}

ここでVBコードとして見つけました。Javascriptに翻訳しただけです。

于 2012-10-24T22:11:53.057 に答える