素数判定機

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の倍数以外の数で割っていくという、 ハイブリッドの試し割り法です。

当初は処理速度優先で、1000万以下の素数リストを持たせていました。 これだと確かに高速に判定できるのですが、ファイルサイズが5.6MB、 gzip圧縮しても1.6MBと大きめで、初期表示に時間がかかり問題でした。 そのため、処理速度を犠牲にしハイブリッド方式にしました。

処理速度は14桁の素数(92709568269121)で、もともと35msec程度だったのが、 80msec程度と倍以上に遅くなりました。しかし、ファイルサイズが1/10程度になり、 初期表示が比較的スムーズに行えるようになり、さらに対応桁数も2桁増やせたので メリットも大きかったと思っています。

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

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

関連

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

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

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


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