JavaScriptで整数を素数のべき乗の積として表現する方法

本記事では、正の整数を受け取り、その数を素数のべき乗の積として表す文字列を返すJavaScript関数の作成方法を解説します。

問題の概要

任意の正の整数 n を引数として受け取り、次の形式の文字列を返す関数を実装します。

n = "(p1**n1)(p2**n2)...(pk**nk)"

ここで p1〜pk は素因数となる素数、n1〜nk はそれぞれに対応する指数です。「a**b」は「a の b 乗」を意味します。

例

例として 86240 を渡した場合、この数は次のように素因数分解できます。

86240 = 2⁵ × 5 × 7² × 11

したがって、期待される出力は次のとおりです。

(2**5)(5)(7**2)(11)

実装コード

以下は、素因数分解を行い、指定された形式の文字列を生成するJavaScriptの実装例です。

const primeFactors = (num) => {
  let result = '';
  let n = num;
  for (let p = 2; p <= n; p++) {
    // 割り切れない場合は次の候補へ
    if (n % p !== 0) continue;
    let exponent = 0;
    // 同じ素数で割り切れる限り割り続ける
    while (n % p === 0) {
      n /= p;
      exponent++;
    }
    result += exponent > 1 ? `(${p}**${exponent})` : `(${p})`;
  }
  return result;
};

console.log(primeFactors(86240));

出力

(2**5)(5)(7**2)(11)

コードの解説

• 素因数の探索： 2から順に整数 p を調べ、n が p で割り切れる場合だけ処理を進めます。
• 指数のカウント： whileループで同じ素数 p で割り切れる間、n を割り続け、割った回数を指数として記録します。
• 文字列の生成： 指数が2以上の場合は「(p**指数)」、指数が1の場合は「(p)」の形式で結果の文字列に連結します。

このアルゴリズムでは、複雑な素数判定用の補助関数を用意しなくても、試し割り法だけで素因数分解から整形済み文字列の生成までをシンプルに実現できます。