素数判定機

16桁以下の自然数について素数かどうか判定します

sample

 

  • 10桁のメルセンヌ素数:2147483647
  • 14桁の大きな素数:92709568269121
  • 16桁の大きな素数:9007199254740997
  • 13桁の合成数:1565912117761 = 1162193×1347377
  • 16桁の合成数:8635844967113809 = 89652331×96325939
※JavaScriptのみで判定しています。入力値のサーバ送信などしていません。

概要

1京未満(16桁以下)の自然数について、素数かどうか判定を行うツールです。 このページでは「決定的素数判定法」により判定を行っています。※最近は届いたマイナンバーが素数かどうか確認して一喜一憂する遊びに使われているようです。

※正確には9007199254740991以下の数値の判定になります。 MAX_SAFE_INTEGER(9007199254740991)を超える数値は正確に表せる保証がなく、 9007199254740993以上は最下位ビットが失われ偶数になってしまうためです。

※類似サービスを提供する他サイトよりも、 (おおむね)より多くの桁をより高速に素数判定ができます (私がリサーチした範囲では、世界最速でした。 もしもこのページより速く処理できるサイトがあれば教えていただきたいです)

補足

コメント

「決定的素数判定法」は、「1京未満(16桁以下)」を上限としました。 JavaScriptの数値型は内部で倍精度浮動小数点数を使用しており、整数が正確に表せるのは2^53 つまり9,007,199,254,740,992(16桁・約9007兆1993億)までという制約があるので、この機能では一応16桁を上限としました。

9,007,199,254,740,992を超えると偶数になってしまいます。それを確認するサンプルとして、 JavaScriptで正常に表現できる最大の素数「9007199254740881」と JavaScriptで正常に表現できない最小の素数「9007199254740997」をサンプルリストに加えました。

※それ以上の値を計算するためのライブラリもいくつかあるのですが、独自色が強く 信頼性が不明で、またライセンスもよく分からないので、今回は使用を見送りました。

「決定的素数判定法」のアルゴリズムは、まず100万以下の素数リストを持ちそれで割っていき、 素数リストの最大値を超えたら「2, 3, 5, 7の倍数以外の数で割る」という、ハイブリッドの試し割り法です。 「JavaScriptでの素数判定アルゴリズムのパフォーマンステスト」 のページで、(ほぼ同じ内容の)ソースの確認と、アルゴリズムの実行速度比較測定ができます。 アルゴリズムに興味のある方はこちらも参考にしてみてください。

当初は処理速度優先で、1000万以下の素数リストを持たせ、それだけで判定していました。 これだと確かに高速に判定できるのですが、ファイルサイズが5.6MB、 gzip圧縮しても1.6MBと大きめで、初期表示に時間がかかり問題でした。 そのため、処理速度を犠牲にしハイブリッド方式にしました。 処理速度は倍以上に遅くなりましたが、初期表示が比較的スムーズに行えるようになり、 さらに対応桁数も2桁増やせたのでメリットも大きかったと思っています。

また、ハイブリッド化当初は「2, 3, 5の倍数以外で割る」というアルゴリズムだったのですが、 2017/07/22に「2, 3, 5, 7の倍数以外の数で割る」に変更しました。 その結果、さらに15%程度処理速度が向上しました。

また、JavaScriptで正常に表現できる最大の素数「9007199254740881」の判定も 0.75秒程度(Chrome43, Win7, Core i7)の時間で処理できたので、 最大負荷時の処理性能としても問題ないと判断しました。

当初は「決定的素数判定法」「フェルマーテスト」「ミラー-ラビンテスト」の3機能を 1つのページにまとめていたのですが、内容が多いので、 「素数判定機 (決定的素数判定法)」と 「巨大数向け素数判定機 (フェルマーテスト・ミラー-ラビンテスト)」で別のページに分離しました。

関連

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

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

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


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