JavaScriptで素因数分解をしてみたい…
そして色々ググっていくと、
良さげなアルゴリズムを見つけました。
それがosa_k法アルゴリズム
次のような特徴をもってます。
- n以下の任意数を素因数分解できる
- 他アルゴより高速実行可能
- ただしメモリ使用量が多いらしい
JavaScriptでの実装方法をまとめてみます。
このページの目次
osa_k法での素因数分解の流れ
具体的なコードの前にアルゴリズムの概要から
これはエラトステネスの篩を応用したものです。
例えばN以下の整数を素因数分解したいとします。
その時のフローチャートは以下の通りです。
- 最小素因数を管理するminFactor配列
初めにエラトステネスの篩(ふるい)で使用する配列 minFactor を用意する。ひとまず0～nの数で埋めていくことにする
- そのminFactorをふるいにかける
2以上N以下の整数をiとおき、 minFactor[i]===i ならiの倍数の要素に i を代入する。例 : 2の倍数 4, 6, 7, 8 ,10... には 2を代入する。やることはエラトステネスの篩を全く同じ
- 素因数分解を実行
たとえば m という数を素因数分解したいなら、 minFactor[m] を m でひたすら割っていけばいい。割り切れた時点で素因数分解終了ということ
このような流れになってます。
osa_k法のJavaScriptでの実装例
言葉だと分かりにくいので…
具体的なコードで示すことにします。
▼ osa_k法のJS実装コード例
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/** * 2～nのそれぞれの数の最小素因数を求める。 * そしてそれを配列として返す **/ function sift(n){ /// 最小素因数を管理する配列 const minFactor = []; /// ひとまず必要な領域の配列埋める for(let i=0; i<=n; ++i){ minFactor.push(i) } /// 各数の最小素因数を求める /// やることはエラトステネスの篩と同じ for(let i=2; i**2<=n; ++i){ if(minFactor[i] === i){ for(let j=2; i*j<=n; ++j){ if(minFactor[i*j] > i){ minFactor[i*j] = i; } } } } return minFactor; } /** * 引数mを素因数分解する **/ function factorize(m){ /// 素因数分解の結果 const result = []; /// 最小因数リスト const minFactor = sift(m); /// 割り切れるまで素因数分解 while(m > 1){ const factor = minFactor[m]; result.push(factor); m /= factor; } return result; } console.log(factorize(2023)); /// => [7, 17, 17] |
何をしてるかは先ほど説明しました。
エラトステネスの篩は素数を効率よく求めるだけじゃなく、こういう風に素因数分解のアルゴリズムとしても利用できます。
とても分かりやすいアルゴリズム
ただしメモリ使用量がでかいのが欠点
ただこのosa_k法には致命的欠点があります。
それはメモリ使用量がデカすぎること
分解対象が大きな数ほど巨大な配列が必要です。
▼ この部分のコード
|
1 2 |
/// ひとまず必要な領域の配列埋める for(let i=0; i<=n; ++i){ minFactor.push(i) } |
▼ それは以下の記事でも指摘されている
したがって通常の素因数分解よりも高速に素因数分解することができる。（ただしメモリの制約上 MAX の値が 10^8程度までにおさまる必要がある）
良い方法だと思ったけど、こんな欠点が…
普通に考えればそうですよね。だって10兆とか素因数分解しようとすると10兆個の要素をもつ配列が必要なわけです。メモリは有限だから現実的じゃありません。
目安として 10^8 程度に収める必要があるようです。
この方法は欠点が多くて実用的ではない
ということで結論としては、
- 素因数分解は高速に実行できる
- でもメモリ使用量もデカすぎる
- メモリは有限だから巨大数は不可
- 賢い方法だけど実用性ほぼなし
スタンドアロンで動くならともかく、
JavaScriptはブラウザ上で実行されるものです。
※ ただしNode.jsなら話は変わってくる
メモリ使用量はさらに限られます。
70桁を一瞬で素因数分解できるアルゴリズム？
素因数分解の最強のアルゴリズムは何なのか…
その答えを自分は持っていません。
驚いたのはこんなツールが実在してることです。
▼ 素因数分解ツール
なんと70桁を一瞬で素因数分解できます！
メモリ使用量・計算量的にosa_kを採用してるわけもないし、本当にどのようなアルゴリズムで動いているのか興味深いです。
もし何か知ってる人がいれば教えてください。
以上、JavaScriptで素因数分解でした。ではまた
