【JavaScript】素因数分解をするコードを作成してみた

更新日:2023/07/21

JavaScriptで素因数分解するコードを作成したので、紹介します。

 

概要

基本的には元となる値を一番小さい素数2で割り切れなくなるまで割り、割った回数を記憶します。
次に素数3,5,7...と繰り返して、残りの値が素数になるまで繰り返します。

実際の処理では素数を全てリスト化するのは現実的ではないので、2および奇数値で割っていきます。

また、割る数は現在の値の平方根までとします。
この理由は、次のページの最後で解説しているので読んでみてください。

 

JavaScriptで素因数分解するコード

ということで作成したのが次のコードです。

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

    const result = [];

    let count = 0;
      // 2で割る
    while( n % 2 === 0 ){
        ++count;
        n /= 2;
    }
    if( count > 0 ) result.push( {number:2,count:count} );

      // 奇数で割る
    let max = Math.floor(Math.sqrt( n ));
    for( let i = 3 ; i <= max ; i += 2 ){
        if( n % i === 0 ){
            count = 0;
            do{
                ++count;
                n /= i;
            }while( n % i === 0 );
            result.push( {number:i,count:count} );
            max =  Math.floor(Math.sqrt( n ));
        }
    }
    if( n !== 1 ) result.push( {number:n,count:1} );
    return result;
}

2と奇数のループは、効率を考えると二つにわかれますね。
また、奇数のループ内はif文が一つになるように工夫しています。
do..while構文とか、あまり使わないかな?

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

作成した関数を実行してみます。

console.log( primeFactorization(16) );
 // 結果: [ { number: 2, count: 4 } ]

console.log( primeFactorization(5963) );
 //  結果:[ { number: 67, count: 1 }, { number: 89, count: 1 } ]

console.log( primeFactorization(282828) );
 //  結果:[ { number: 2, count: 2 },  { number: 3, count: 1 },
 //         { number: 7, count: 2 },  { number: 13, count: 1 },
 //         { number: 37, count: 1 } ]

console.log( primeFactorization(10000000) );
 // 結果: [ { number: 2, count: 7 }, { number: 5, count: 7 } ]

console.log( primeFactorization(999491) );
 // 結果: [ { number: 999491, count: 1 } ]

上手く動いてくれました。

更新日:2023/07/21

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

スポンサーリンク

記事の内容について

null

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

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

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

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

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

 

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