JavaScriptで次のことがしたい。
- ある数、例えば 18 がある
- その全ての約数を求めたい
- 例えば 1,2,3,6,9,18 みたいに…
それにはいくつか手順が必要です。
ググっても中々答えが出てこないので、
自分でロジック／コードを考えてみました。
JavaScriptに限らず汎用的な手法です。
このページの目次
１．初めに数を素因数分解する
全約数を求めるには下準備が必要です。
それが対象の数を素因数分解すること
具体的には次のようなコードです。
▼ このようなコードを書いた
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/** * ある数nを素因数分解して結果を返す **/ function factorize(n){ /// nの各素因数とその個数を記録する配列 const arr = []; /// nを素因数分解する for (let i=2; i*i<=n; ++i) { if (n % i == 0) { var count = 0; while (n % i === 0) { n /= i; count += 1; } arr.push({ count, factor:i }); } } /// nが素数である場合 if (n > 1) { arr.push({ count:1, factor:n }); } return arr; } |
▼ いくつかの数を素因数分解する例
|
1 2 3 4 5 6 7 8 9 10 11 12 |
console.log(factorize(12)) // => [ // {count: 2, factor: 2} // {count: 1, factor: 3} // ] console.log(factorize(300)) // => [ // {count: 2, factor: 2} // {count: 1, factor: 3} // {count: 2, factor: 5} // ] |
このような関数を作成しました。
上記の例で説明するなら、12を素因数分解すると 2^2*3^1 とあらわせるので [{count: 2, factor: 2},{count: 1, factor: 3}] のような素因数・その指数のペア配列が返ってきます。
ちなみに上記はかなり簡素なアルゴリズムです。
▼ 速度を求めるならosa_k法など色々ある
https://pisuke-code.com/js-factorise-number-by-osa-k/
ひとまず素因数分解さえできればOK。
こうすると約数が求めやすいです。
２．全ての約数を素因数から求める
そしたら全ての約数を求めてみます。
本当はあまり良くないけど、
再帰を使うと超簡単に求めること可能です。
▼ 次のようなコードを書いた
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
function findDivisors(n){ /// 素因数分解 const arr = factorize(n); /// 全ての約数を取得して返す const divisors = []; recurseDivisors(0, 1, arr); return divisors; /// 再帰的に約数を求める関数 function recurseDivisors(index, divisor, arr){ if (index == arr.length) { /// 約数を入れる divisors.push(divisor); return; } /// 素因数から生じる約数を網羅させる for (var i = 0; i <= arr[index].count; ++i) { recurseDivisors(index+1, divisor, arr); divisor *= arr[index].factor; } } } |
このような関数で全約数がゲットできます。
問題なのは再帰的（recursively）なロジックであることです。一見スマートに見えるけど、実は再帰ってパフォーマンス的に最悪なですよね(-_-;)
詳しくは次記事でも書きました。
▼ 再帰なしでフィボナッチ数を求める
もしパフォーマンスを向上させたいなら…
再帰を使わないロジックに変更してください。
３．色々な数の全約数を求めてみた
上記の関数を使った結果がこれです。
▼ 適当な数で全約数を求めた
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
divisors = findDivisors(12); console.log(divisors) /// => [1, 3, 2, 6, 4, 12] divisors = findDivisors(511); console.log(divisors) /// => [1, 73, 7, 511] divisors = findDivisors(2023); console.log(divisors) /// => [1, 17, 289, 7, 119, 2023] divisors = findDivisors(96709); console.log(divisors); /// => [1, 997, 97, 96709] divisors = findDivisors(600011); console.log(divisors); /// => [1, 600011] |
という感じで全ての約数が求められました。
実用的な範囲はMAX_SAFE_INTEGERまで
上記コードには実用的範囲の制限があります、
目安としては Number.MAX_SAFE_INTEGER まで
▼ Number.MAX_SAFE_INTEGERの概要
Number.MAX_SAFE_INTEGER 定数は、JavaScript における安全な整数の最大値 (2^53-1) を表します。もっと大きな整数には、 BigInt を使用することを検討してください。
2^53-1 = 9007199254740991
ここまでが実用的な範囲です。
それ以上でも期待通りに動くこともありますが、安全ではないので素因数分解できる保証はありません。エラーは出ないけど答えは間違っています。
その点に注意してください。
巨大数にも対応したいならBigIntを使う
上記の説明にあるように、
巨大数は BigInt で扱えます。
▼ JavaScriotでのBigInt型
BigInt 値は、単に BigInt と呼ばれることもありますが、 bigint プリミティブです。整数リテラルの末尾に n を追加するか、 BigInt() コンストラクターを呼び出し、整数値または文字列値を与えることで生成することができます (ただし new 演算子なしで)。
引用元 ： https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/BigInt
ここまでのコードも BigInt に置換可能。
興味のある人は試してみてください。
巨大数では素因数分解の速度も重要
もし巨大数のすべての約数を求めたいなら…
素因数分解の速度がとても重要です。
- 巨大数は素因数分解に時間がかかる
- どんなアルゴリズムを使うかが重要
- メモリ使用量にも注意しないといけない
素因数分解は１つの分野になってます。
知ってる人は多いと思いますが、素因数分解は桁数が多いほど難しいです。そして300桁のような桁数になると現実的な時間で計算できません。それを応用したのがRSA暗号ですね。
巨大数の約数を求めるのは不可能かも
でも50桁程度なら頑張れば求められます。
ってことでJavaScriptで全約数の求め方でした。
