素数判定機

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

sample

 

  • 10桁のメルセンヌ素数:2147483647 = 231-1
  • 12桁のユークリッド素数:200560490131 = 31×29×23×19×17×13×11×7×5×3×2+1
  • 14桁の素数:92709568269121
  • 16桁の素数:9007199254740997
  • 13桁の合成数:1565912117761 = 1162193×1347377
  • 16桁の合成数:8635844967113809 = 89652331×96325939

概要

1京未満(16桁以下)の自然数について、素数かどうか判定するツールです。 「決定的素数判定法」により判定しています。

※正しく判定できるのは、9007199254740992以下になります。

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

※素数の生成は「素数生成機」をご利用ください。 9007199254740993以上の数値に対する素数の判定は「巨大数向け素数判定機」をご利用ください。

補足

コメント

JavaScriptの数値型は内部で倍精度浮動小数点数を使用しており、整数を正確に表せる最大値(MAX_SAFE_INTEGER)は、 253 - 1、つまり9007199254740991(16桁・約9007兆1993億)となっています。 それを超える数値は丸め処理が行われるため、内部ではどんな数値も必ず偶数になります。

ちなみにMAX_SAFE_INTEGERは9007199254740991となっていますが、9007199254740992は最下位ビットが0であるため、 丸めが発生しても値は変わりません。そのため整数を正確に表せる最大値は実質的にはMAX_SAFE_INTEGER + 1の9007199254740992になります。

そのような制約があるため、この機能では「1京未満(16桁以下)」を上限としました。 9007199254740993~9999999999999999も入力できますが、素数かどうかにかかわらず必ず 「素数ではありません。少なくとも2で割れます」と判定してしまいます。

すでに述べましたが、JavaScriptの数値型は9007199254740992を超える数値は内部で必ず偶数になります。 それを確認するサンプルとして、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)の時間で処理できたので、 最大負荷時の処理性能としても問題ないと判断しました。

関連・参考リンク

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

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

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


このページはお役に立ちましたか?
自由メッセージ
認証コード 必須
画像のひらがな一文字を入力してください。拗音・促音・濁点・半濁点はありません。
※サンプルの追加・ツール改善の参考に利用させていただきます。