【JavaScript】数値の約数をすべて求める関数の実装方法

はじめに

本記事では、正の整数を1つ引数として受け取り、その数を余りなく割り切れるすべての数(約数)を配列として返すJavaScript関数の実装方法を解説します。

問題の定義

作成する関数は、正の整数を唯一の引数として受け取ります。そして、入力された数値を完全に割り切れるすべての数値を要素とする配列を構築して返す必要があります。

例えばー

入力が次の数値だった場合:

const num = 12;

期待される出力は以下のとおりです。

const output = [1, 2, 3, 4, 6, 12];

12の場合、1・2・3・4・6・12の6つの整数が12を割り切れるため、これらが約数となります。

実装コード

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

const findFactors = (num = 1) => {
    let half = Math.floor(num / 2);
    const res = [1]; // 1はすべての数の約数なので、あらかじめ含めておく
    let i, j;
    num % 2 === 0 ? (i = 2, j = 1) : (i = 3, j = 2);
    for (i; i <= half; i += j) {
       if(num % i === 0){
          res.push(i);
       };
   };
   res.push(num);
   return res;
};
console.log(findFactors(12));

コードのポイント解説

この実装には、無駄な計算を省くための工夫がいくつか施されています。

• 探索範囲を半分に制限: Math.floor(num / 2) により、num / 2 より大きい約数は num 自身以外に存在しないため、ループは半分までで十分です。
• 1を初期値に設定: すべての正の整数は1で割り切れるため、結果配列の初期値として1を入れておきます。
• 偶数・奇数で処理を分岐: 入力が偶数の場合は2から1刻みでチェックし、奇数の場合は3から2刻み(奇数のみ)でチェックします。奇数の約数は必ず奇数になるため、偶数候補をスキップすることで計算量を削減できます。
• 自分自身を最後に追加: どんな正の整数も自分自身で割り切れるため、ループ終了後に num を配列へ追加しています。

出力結果

コンソールには以下のように出力されます。

[ 1, 2, 3, 4, 6, 12 ]

このアルゴリズムの計算量は O(n/2)、つまり O(n) であり、単純に1からnumまで全件チェックする方法より効率的です。さらに高速化したい場合は、「平方根までのペアを利用する」手法(O(√n))もありますので、大きな数値を扱う際は検討してみるとよいでしょう。