気軽に素因数分解
本格的なのは難しくても、ちょっと123456789を素因数分解したいときとか用に
素因数分解してくれる何かが欲しいと思っていた。
こことかこことかこことか、よさそうなのはあるけど。
まず、エラトステネスのふるいで素数を作る。
1bitに1つの数を割り当てたが、よく考えたら偶数は除くべきだった。
10^nまでの素数の個数で正しい個数になっているか確認。
まあ、奇数で順に割っていっても、それほど速度は変わらない。
あとは普通に割っていく。
JavaScriptの倍精度浮動小数点で厳密に扱える整数は253なので、
9000兆くらいまで、運がよければ分解できる。
コンマ数秒で確実に素因数分解できるのは1兆まで。意外といける。
ところで、9000000000000001にMath.floorかますと9000000000000000になるの何で。
9000000000000003は、ちゃんと9000000000000003になるのに。
あとは12章 素因数分解アルゴリズムとか読んで高速化か。
分解する前に素数判定しておくのも必要だよな。
難しくて吐きそう。
