2

パラメータnとqを取り、q以上のnを除算する最小の素数を返すfindFirstという関数が必要です。そこで、最初に、数が素数であるかどうかを示す関数を作成しました。

var isPrime = function(n){
    if(n === 1){
        return false;
    }
    else if (n === 2 || n === 3){
        return true;
    }
    else {
        for(i=2; i < n; i++){
            if(i * i >= n){
            for(j=2; j<=i; j++){
                    if(n % j === 0){
                        return false;
                    }
                }
            return true;
            } 
        }
    }
};

これをより効率的にする他の方法があるかもしれませんが、私はこの関数が問題ではないと確信しています。

したがって、この関数を使用して、findFirstを作成する最初の試みを行いました。

var findFirst = function(n,q){
    var p = q;
        while(n % p !== 0 || isPrime(p) === false){
            p++;
        }
    return p;
};

この関数は機能しますが、数値が大きいとクラッシュします。たとえば、入力時にクラッシュします（6310545154、3）。ちなみに6310545154の素数冪分解は2*3155272577です

そこで、最初に数の素因数をリストする別の関数を作成しました。

var getFactors = function(n){
    var factors = [];
    var k = n;
    var p = 2;
    while(isPrime(k) === false && k !== 1){
        while(k % p !== 0 || isPrime(p) === false){
            p = p+1;
        }
        while(k % p === 0){
            k = k/p;
        }
        factors.push(p);
    }
    if(isPrime(k) === true){
        factors.push(k);
        return factors;
    }
    if(k === 1){
        return factors; 
    }
};

そして今、findFirstでの2回目の試みは次のとおりです。

var findFirst = function(n,q){
    var array = getFactors(n);
    var p = 0;
    for(i = 0; i < array.length; i++){
        if(array[i] >= q && p === 0){
            p = array[i];
        }
    }
    return p;
};

これはうまくいきます。上記の大きな数値ではクラッシュせず、結果を即座に計算します。なぜこれが起こるのか誰かがわかりますか？私の最初の試みの「while」ループは、getFactors関数の「while」ループの1つと非常に似ているようです。そして、2番目の試みははるかに複雑に見えます。

4

5 に答える 5

3

2 番目のプログラムは、大きな素因数が 1 つしかないため、すぐに戻ります。（すべて）小さな素因数が見つかると、すぐにループを終了します。最初のプログラムは、3 から 3155272577 までずっとカウントしないと、それが因数であることがわかりません。2147483647 以降は、整数演算から浮動小数点演算に切り替える必要があるため、さらに遅くなります。

ご了承ください

var isPrime = function(n) {
    ...
};

関数を作成する珍しい方法です。通常、あなたは書くでしょう

function isPrime(n) {
    ...
}
于 2012-09-01T23:17:17.043 に答える
0

2 回目の試行は実行p = p+1;されず、実際にはwhileこのgetFactors部分で 2 回だけ実行されます。

   while(k % p !== 0 || isPrime(p) === false){
        p = p+1;
    }

p'3' から の すべての数を最初の試行3155272577で素数と因子についてテストする必要がある最初の試行とは異なりますn。

    while(n % p !== 0 || isPrime(p) === false){
        p++;
    }

なんで？
2 番目の試行は var p = 2;and で始まります。これは、 andが両方var k = n;であることを意味します(when )(k % p === 0)isPrime(p)truen=6310545154

while(isPrime(k) === false && k !== 1){
    while(k % p !== 0 || isPrime(p) === false){
        p = p+1;                                               /*  this is never executed for findFirst(6310545154, 3)  */
    }
    while(k % p === 0){
        k = k/p;
    }
    ...

そしてk = k/p;すぐ に外側を終了kする3155272577while(isPrime(k) === false ...

2 回目の試行で同じ異常な時間の動作を観察するには、 と を使用
var factors = [2];しvar p = 3;ます。

ref: エラトステネスのふるい - ウィキペディア

于 2014-05-09T23:12:21.780 に答える
0

コードにはたくさんのバグがあります-たとえば、この方法iはグローバル変数です

for(i=2; i < n; i++){

あなたがしたいことは

for(var i=2; i < n; i++){

じゃあ後で

factors[i] = k;

どこiが定義されていないかなど。

コードを jslint または jshint で実行して、最初に完全に正しくします。

于 2012-09-01T23:17:00.760 に答える
0

正規表現を使用して、素数をすばやく確認できます。

function isPrimeNumber(n) {
    return !/^1?$|^(11+?)\1+$/.test((new Array(++n)).join('1'));
}

この投稿の詳細をお読みください。

編集：ただし、多数の場合は最適ではないかもしれません。より迅速な解決策のようです。

于 2012-09-01T23:29:11.483 に答える
0

これは質問に直接対処するものではありませんが、応答しないタブはクラッシュと同じではないことを強調することが重要だと思います. 応答しないということは、ページが非常に長い間 JavaScript を実行していることを意味します。

スクリプトを実行せずにスクリプトが完了するかどうかをブラウザーが確実に知る方法はないことを覚えておいてください。これは停止問題と呼ばれ、チューリング完全なプログラミング言語の場合、解決できません。スクリプトを強制終了するブラウザの提案は推測に基づいており、問題のスクリプトが何であれ、これは当てはまります。

于 2012-09-01T23:37:59.493 に答える