こんにちは！
今回は「Javascriptで全ての約数を取得するロジック」についてお伝えしたいと思います。
約数は日常生活の中でもホールケーキのカットやタイムスケジュールなど様々な場面で使われていますよね。
Javascriptで全ての約数を取得するロジック
最短のアルゴリズムで自然数Nの約数を算出するポイントは
1からNまで全てを割って確認する必要はなく、1から√Nまで確認すればよいという点です。
例
例えばN=8の約数を算出する場合、
8 ÷ 1 = 8 あまり0
8 ÷ 2 = 4 あまり0
√8は3より小さいので、1〜2までの割り算をします。
上記式を変形すると、
8 = 8 × 1
8 = 4 × 2
となり、商である8と4も約数であると言えます。
8の約数： 1, 2, 4, 8
実際の約数算出のアルゴリズムを以下に示します。
// 全ての約数を取得する
const getDivisors = (num) => {
const result = [];
for (let i=1; i*i<=num; i++) {
console.log(i, num / i);
if (num % i !== 0) continue;
result.push(i);
if (i !== num / i) {
result.push(num / i);
}
}
return result;
};
console.log('getDivisors(1): ', getDivisors(1)); // getDivisors(1): [1]
console.log('getDivisors(7): ', getDivisors(7)); // getDivisors(7): [1, 7]
console.log('getDivisors(8): ', getDivisors(8)); // getDivisors(8): [1, 8, 2, 4]
これで最小の計算量で全ての約数を算出することができました。
約数の順序は必要に応じて昇順にソートしてあげてください。
以上、お疲れさまでした〜🍵