素因数分解計算機

素因数分解


sample

概要

このページでは、任意の自然数の「素因数分解」を行えます。2以上 1京未満(16桁以下)の整数に対応しています。

正確には9007199254740991以下の数値になります。倍精度浮動小数点数の制約で、 MAX_SAFE_INTEGER(9007199254740991)を超える数値は正確に表せる保証がなく、 9007199254740993以上は最下位ビットが失われ偶数になってしまうためです。

入力チェックで、MAX_SAFE_INTEGER(9007199254740991)を超える数値をはじこうか迷ったのですが、 MAX_SAFE_INTEGERを超える値を使うとどうなるかの参考にもなるので、入力ができる状態で残しました。

補足

コメント

このページの処理の実装は紆余曲折ありました。 当初は1000万までの素数リストを持ちそれで割る方法をJavaScriptで実装しました。 処理速度は極めて高速なのですが、データファイルサイズが 5.6MBもあり、ネットワーク転送に時間がかかり問題でした。 また、処理上限は100兆未満(14桁以下)としていました。

これを解決するため1000万までの素数リストを持つロジックを PHP側で実装することにしたのですが、PHPでは20億程度の数値までしか扱えず断念。 しかし翌日ランニング中に「20億程度の数値までしか扱えなかったら言語として使い物にならない。 何か代替方法があるはず」と思い直し調べると、「BC Math 関数」なる物を使えば 計算可能ということが分かり、これを使って実装。しかし自宅サーバー上では成功するも、 レンタルサーバー上では、素数リストのせいでメモリ不足でエラーが発生。サーバーの制約で128MBが上限とのこと…。

サーバー側の制約でのトラブルや仕様変更はこれで3度目です。 OSの違いやバージョン差によるトラブルならよくある話ではありますが、 サーバーの独自制約によるトラブルに、短期間に何度も悩まされたのは初めてでした。 無料・格安サーバーは使ってみないと分からないトラブルが結構発生するものですね…。

そのためしばらくは、「1000万までの素数リストを使う方法をJavaScriptで実装」を採り、 gzip圧縮して転送するなど微妙な改善でしのいでいました。しかし「奇数で割る方法」だと 処理速度は多少遅いもののJavaScriptではおおむね16桁まで処理可能なことを知り、 「100万までの素数リストで割り、それ以上は2, 3, 5の倍数以外で割る」方法に変更しました。

その結果、大きな素数の場合には少し時間がかかるようになったものの、 読み込み速度は速くなり、処理上限も「1京未満(16桁以下)」とすることが出来ました。 処理速度や一つの方法にこだわるのではなく、各ロジックのメリット・デメリットを見極め それを活かして最適な組み合わせを探すことも重要だと実感しました。

処理上限の「1京未満(16桁以下)」はJavaScriptで値を保持できる上限に基づいています。 これを「100万までの素数リストで割り、それ以上は2, 3, 5の倍数以外で割る」方法 をPHPで実装し、かつ「BC Math 関数」を使えば、さらに大きな桁の数値の 処理をすることが出来るのではないかと思ってはいます。

しかし同様の機能を提供しているサイトでは、上限が10桁程度だったり、 入力は受け付けても「7334498792633」はタイムアウトになってしまうサイト (素因数分解 - 高精度計算サイト カシオ計算機(株))ばかりでした。 ので、「1京未満(16桁以下)」まで処理できるのは優秀な方かなと思っており、 現段階では更なる処理能力の向上は考えていません。

関連

ちょこっとアンケート&メッセージ

このページに関するちょっとした感想または、要望、バグ・間違いの指摘、 質問・その他お問合せ等は、下記の送信欄からお送りください。 返信をご希望の方は「こちらのページ」からメッセージをお送りください。

「このページはお役に立ちましたか?」のアンケートとメッセージのどちらか一方でかまいません (両方書いていただけるとよりうれしいです)。お気軽にご利用ください (感想・フィードバック・どんな用途で使用したかなどをいただけると作成・運営の励みになります!)


このページはお役に立ちましたか?