【JavaScript】素数の判定と範囲内の素数を求める方法

更新日:2023/07/21

JavaScriptである値が素数かどうかの判定と、特定の範囲にある素数を抽出する方法をお伝えします。

 

素数かどうかの判定

素数は1より大きい整数で、自分自身のみ割り切れるものです。
そのため、2から自分自身-1までの整数値で割って割り切れたら、素数ではありません。

実際には、判定する値の平方根まで確認すれば十分です。
(理由はこちら

また、2以外の偶数値で割り切れるなら2で割り切れているはずなので、奇数のみで余り判定すれば十分です。

以上の条件で、作成したのが次のコードです。

const isPrimeNumber = number =>{
    const n = Number( number ); // 数値変換
    if( !Number.isInteger(n) || n <= 1 ) return false;

    if( n === 2 ) return true; // 2は素数
    if( n % 2 === 0 ) return false;

    const max = Math.floor( Math.sqrt( n ) );
        
        // 3から奇数でループ
    for( let i = 3 ; i <= max ; i += 2 )
        if( n % i === 0 ) return false;
    
    return true;
}

引数は数値文字列にも対応しています。
Number型のみでいいのなら、最初の数値変換は削除できます。

この関数を使用して、1から100までの素数をピックアップしてみます。

const primeNumber = [];

for( let i = 1 ;i < 100 ; i++)
    if( isPrimeNumber(i) ) primeNumber.push( i );

console.log( primeNumber );
// 結果: [
//    2,  3,  5,  7, 11, 13, 17, 19,
//   23, 29, 31, 37, 41, 43, 47, 53,
//   59, 61, 67, 71, 73, 79, 83, 89,
//   97
// ]

 

範囲内の素数を求める

次に指定された範囲内の素数を求めます。

これについては、前項で1から100までの範囲で求めています。
しかし効率が悪いので、効率を考えながら関数化します。

const getPrimeNumberRange = (start,end)=>{
    start = Number(start);end = Number(end);
        // 整数チェック
    if( !Number.isInteger( start ) || !Number.isInteger( end )) return null;

        // 範囲チェック(入れ替え)
    [start,end] = [start <= 1 ? 2 : start, end <= 1 ? 2 : end];
    if( start > end )  [start,end] = [end , start];

    const result = [];

        // 開始が偶数かチェック
    if( start % 2 === 0 ){
        if( start === 2 ) result.push( 2 );
        start ++; // 奇数からスタートさせる
    }
    if( start > end ) return result;

    for( let n = start ; n <= end ; n += 2 ){
        const max = Math.floor( Math.sqrt( n ) );
        let prime = true;
        for( let i = 3 ; i <= max ; i += 2 ) {
            if( n % i === 0 ) {prime=false;break;}
        }
        if( prime ) result.push( n );
    }
    return result;
}

前半は引数チェックです。
整数かどうかを確認したあと、開始と終了範囲チェックをしています。

次に開始が偶数なら、+1して奇数から開始するように調整します。

次に開始から終了まで順番に素数判定します。
ただし偶数は素数ではないことが確定しているので、飛ばします。

 

エラトステネスの篩(ふるい)

範囲内の素数を検索する方法としてエラトステネスの篩が知られています。
ただし、開始位置が2からになります。

仕組みとしては単純で、2から終了位置の平方根までループをしていき、倍数、つまり素数でない値にフラグを立てていきます。
そして最後までフラグが立たなかった値が素数になります。

とりあえず、JavaScriptでコードを作成してみます。

const getPrimeNumberRange2 = end =>{
    const n = Number( end ); // 数値変換
    if( !Number.isInteger(n) || n <= 1 ) return null;
    if( n === 2 ) return [2];

    const flgMap = [];
    const max = Math.floor( Math.sqrt( n ) );

    const result = [2];

        // エストステネスの篩 
    for( let i = 3 ; i <= max ; i+= 2 ){
        if( flgMap[i] === undefined ){
            result.push( i ); // 素数確定
                // 倍数にフラグセット
            for( let j = i * 2 ; j <= end ; j += i ){
                flgMap[j] = true;
            }
        }
    }
        // maxの次の奇数値からフラグが立っていない値を抽出
    for( let i = max + ( max % 2 === 0 ?  1 :2 ) ; i <= end ; i+= 2 ){
        if( flgMap[i] === undefined ){
            result.push( i );
        }
    }

    return result;
}

多くのプログラミング言語は、配列を指定範囲で確保して何らかの値で初期化します。

しかしJavaScriptの配列はそんな必要はありません。
フラグ立てするもののみインデックスを作成して、undefined以外の値をセットすればOKです。

ただ、配列のインデックス作成と値を取り出す処理が比較的重いです。
TypedArrayに置き換えることも検討するとよいですね。
(実際にどちらの方法が速いのかは、未検証です)

なお、配列にしろTypedArrayにしろ、エラトステネスの篩はメモリを大量に消費します。
メモリ確保に失敗してエラーになる可能性も考慮する必要がありますね。

 

なぜ平方根まで確認するのか

素数判定で平方根より大きい値をチェックしなくてもよいのか、解説してみます。

例えば120の平方根は、10.954451150103322です。

この値以降の数値で120を割ってみます。

120 / 12 → 10

12で割り切れました。
120が素数でないことがわかりました。

ですがよく見ると、商が10です。
そのため、10で割り切れるか確認した時点で、素数でないことが判定されているはずです。
次のような計算ですね。

120 / 10 → 12

同様に、割る数を増やしていきます。

120 / 15 → 8
120 / 20 → 6
120 / 40 → 3

このように、割る数が増えると商が小さくなっていきます。
つまり、平方根以降の値で割り切れるなら、すでに他の値で割り切れているのです。
そのため、平方根以降を確認する必要がありません。

120だけではなく、他の値も同じような結果になります。

更新日:2023/07/21

書いた人(管理人):けーちゃん

スポンサーリンク

記事の内容について

null

こんにちはけーちゃんです。
説明するのって難しいですね。

「なんか言ってることおかしくない?」
たぶん、こんなご意見あると思います。

裏付けを取りながら記事を作成していますが、僕の勘違いだったり、そもそも情報源の内容が間違えていたりで、正確でないことが多いと思います。
そんなときは、ご意見もらえたら嬉しいです。

掲載コードについては事前に動作確認をしていますが、貼り付け後に体裁を整えるなどをした結果動作しないものになっていることがあります。
生暖かい視線でスルーするか、ご指摘ください。

ご意見、ご指摘はこちら。
https://note.affi-sapo-sv.com/info.php

 

このサイトは、リンクフリーです。大歓迎です。