2024年を記念して2024をjsで素因数分解してみる #初心者

はじめに

なんと2023年が終わり2024年になってしまいました。
ということで2024を素因数分解します。

目的

ここでは任意の2以上の自然数に対して素因数分解(ついでに素数判定も)を行うプログラムをjsで作成します。

実装方法

今回は速度は気にせず、巨大な数に対する素因数分解も少ないと考えているので、最も単純な素朴法(試し割り法)を用いていきます。
ρ法や篩法は伸びしろとして取っておきます。

実装

document.getElementById("number").addEventListener("change", () => {
  primeFactorization(BigInt(document.getElementById("number").value));
  document.getElementById("number").value = "";
});

function primeFactorization(compositeNum) {
  if (compositeNum <= 1) {
    console.log("2以上の数を入力してください。");
  } else {
    let primeFactors = [];  //約数を格納する配列
    let calcCompositeNum = compositeNum;  //計算用の変数に代入

    //2で割り切れる間2で割る
    while (!(calcCompositeNum % 2n)) {
      calcCompositeNum /= 2n;
      primeFactors.push(2);
    }

    /*
      対象の数(除算後の数)の平方根(※1)まで、3以上の奇数(※2)で割り切れるかみる
      (※1)約数は平方根を対称として、既出の組み合わせとなるため
        ex) 1 * 100 = 100
            2 * 50 = 100
            4 * 25 = 100
            5 * 20 = 100
            10 * 10 = 100
            20 * 5 = 100
            25 * 4 = 100
            50 * 2 = 100
            100 * 1 = 100
      (※2)2より大きい偶数は2の倍数であるため奇数のみの処理
    */
    for (let i = 3n; i * i <= calcCompositeNum; i += 2n) {
      while (!(calcCompositeNum % i)) {
        calcCompositeNum /= i;
        primeFactors.push(i);
      }
    }

    //平方根以上の約数を格納
    if (calcCompositeNum > 1) primeFactors.push(calcCompositeNum);

    //約数を2個しか持たない(1と自身のみ)のは素数
    if (primeFactors.length == 1) {
      console.log(`${compositeNum}は素数です`);
    } else {
      console.log(`${compositeNum}は合成数です`);
      console.log(compositeNum + "=" + primeFactors.join("*"));
    }
  }
  return;
}

結果

入力1

出力1

2024は合成数です
2024 = 2*2*2*11*23

入力2

出力2

2以上の数を入力してください。

入力3

8635844967113809

出力3

8635844967113809は合成数です
8635844967113809 = 89652331*96325939

入力4

7365373222715531

出力4

7365373222715531は素数です

おわり

今回は速度度外視で素因数分解をしていきました。
無事素因数分解することができましたが、速度が非常に遅く、そこが改善点です。
試し割り法以外にもアルゴリズムは沢山あるので、これを機に速度の観点から素因数分解を考えていきたいですね。