JavaScriptで半素数を判定する方法｜素因数分解を使ったチェック関数の実装

本記事では、引数として受け取った数値が半素数（semiprime）であるかどうかを判定するJavaScript関数の実装方法を解説します。

半素数とは

半素数とは、2つの素数の積として表される特殊な合成数のことです。例えば、6（= 2×3）、10（= 2×5）、15（= 3×5）、77（= 7×11）などが半素数に該当します。

また、同じ素数同士の積、つまり素数の2乗も半素数として扱われます。4（= 2×2）、9（= 3×3）、25（= 5×5）などがその例です。

判定アルゴリズムの考え方

ある数が半素数かどうかを調べるには、その数を素因数分解し、素因数の個数がちょうど2つになるかを確認します。小さい数から順に割り算を繰り返す「試し割り法」を使えば、効率よく判定できます。

処理の流れ

1. カウンター変数を用意し、素因数を見つけるたびにインクリメントする
2. 平方根以下の数まで試し割りを行い、割り切れる限り除算を続ける
3. ループ後に残った値が1より大きければ、それも1つの素因数としてカウントする
4. 最終的にカウントが2であれば半素数と判定する

サンプルコード

以下は、与えられた数値が半素数であるかどうかを判定するJavaScriptのコード例です。

const num = 141;
const checkSemiprime = num => {
   let cnt = 0;
   for (let i = 2; cnt < 2 && i * i <= num; ++i){
      while (num % i == 0){
         num /= i, ++cnt;
    }
   }
   if (num > 1){
      ++cnt;
   }
   // カウントが2ならtrue、そうでなければfalseを返す
   return cnt === 2;
}
console.log(checkSemiprime(num));

コードの解説

• for文の条件：カウントが2未満であり、かつ i の2乗が num 以下である間だけループを続けます。これにより計算量を大幅に削減できます。
• while文：同じ素因数が複数回含まれる場合（例：4 = 2×2）にも正しく対応できます。
• ループ後の判定：num が1より大きいまま残った場合、それは1より大きい素因数であるため、カウントに加算します。

実行結果

コンソールには次のように出力されます。141 = 3 × 47 と素因数分解できるため、true が返されます。

true

まとめ

このように、素因数の個数を数えるシンプルなアプローチで、半素数の判定を効率的に実装できます。暗号理論（RSA暗号など）でも半素数は重要な役割を果たすため、その性質と判定方法を理解しておくと役立ちます。