JavaScriptで数値の最大の素因数を求める方法を徹底解説

本記事では、数値を1つだけ引数として受け取り、その数値を余りなく割り切る最大の素数(最大の素因数)を返すJavaScript関数の作成方法を解説します。

問題の概要

作成する関数には、次の要件があります。

• 引数として数値を1つだけ受け取ること
• 引数の数値は必ず合成数(2つ以上の約数を持つ数)であることが保証されていること
• その数値を割り切る最大の素数を見つけて返すこと

具体例

たとえば、引数が 72 の場合、出力は 3 になります。これは、72 を割り切る素数の中で最も大きいものが 3 だからです。

コード例

以下が実際のコードです。

const num = 72;

const largestPrimeFactor = (num) => {
    // √num の切り上げ値から探索を開始
    let res = Math.ceil(Math.sqrt(num));

    // 素数判定用の補助関数
    const isPrime = (num) => {
        let i, limit = Math.ceil(Math.sqrt(num));
        for (i = 3; i <= limit; i += 2) {
            if (num % i === 0) {
                return false;
            }
        }
        return true;
    };

    // 探索開始値を奇数に調整
    res = (res & 1) === 0 ? res - 1 : res;

    // 割り切れて、かつ素数である数が見つかるまで降順で探索
    while (!(num % res === 0 && isPrime(res))) {
        res -= 2;
    }

    return res;
};

console.log(largestPrimeFactor(num));

出力結果

コンソールには次のように表示されます。

3

コードの解説

ここからは、コードがどのように動作しているのかを順番に見ていきます。

1. 探索の開始位置を決める

Math.sqrt(num) で平方根を求め、Math.ceil() で切り上げた値を探索の起点にします。大きな素因数は平方根付近以下に存在することが多いため、ここから下向きに調べることで無駄な計算を減らせます。

2. 素数判定関数 isPrime

isPrime() は、3から始めて2ずつ増やしながら√numまでの奇数で割り切れるかを確認するシンプルな素数判定です。偶数をあらかじめ除外しているため、判定回数を半分に抑えられます。

3. 奇数を降順にチェックして答えを特定

起点の値を奇数に調整した後、res -= 2 で2ずつ減らしながら「num を割り切る」かつ「素数である」という条件を満たす最初の数を探します。条件を満たす数が見つかった時点で、それが最大の素因数です。

注意点：より汎用的な実装

上記のコードは平方根以下の範囲から下向きに探索する方式のため、最大の素因数が平方根より大きいケース(例：10 の場合は 5)では正しい結果が得られない可能性があります。どのような整数にも対応させたい場合は、小さい方から素因数を取り除いていく「素因数分解」ベースのアプローチが有効です。

代替実装：素因数分解によるアプローチ

const largestPrimeFactor = (num) => {
    let maxPrime = -1;
    // 2で割り切れる間は除去し続ける
    while (num % 2 === 0) {
        maxPrime = 2;
        num /= 2;
    }
    // 3以降の奇数で試し割り
    for (let i = 3; i * i <= num; i += 2) {
        while (num % i === 0) {
            maxPrime = i;
            num /= i;
        }
    }
    // 残った数が1より大きければ、それ自体が最大の素因数
    return num > 1 ? num : maxPrime;
};

console.log(largestPrimeFactor(72));  // 3
console.log(largestPrimeFactor(100)); // 5
console.log(largestPrimeFactor(17));  // 17

この方法なら、素数そのものが渡された場合も含めて、あらゆる整数に対して確実に最大の素因数を求めることができます。