素数判定機
16桁以下の自然数について素数かどうか判定します
- 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」をサンプルリストに加えました。
ECMAScript 2020でBigIntが実装され、この新しい型を使えば 9007199254740991を超える整数を正確に扱うことが可能になりました。 そして順次ブラウザにも実装され主要ブラウザ全てで使えるようになったため、2023/1にBigIntを使って実装をしてみました。 すると私のPC(i7-9700)で17桁の素数の判定に1.3秒、18桁の素数の判定に4.0秒、 19桁の素数の判定に10.4秒、20桁の素数の判定に72秒かかりました。
1分を超える処理は使い物にならないので、せいぜい19桁まで。さらにスマホなどでも使えるようにするとなると18桁が限界…。 当サイトではすでに1000桁の素数の判定が可能な「巨大数向け素数判定機」がある中で、 処理上限をたった2桁増やす意味があるのかと考えた末に、リリースを断念しました。
このページでは「決定的素数判定法」を使って判定しています。そのアルゴリズムは、 まず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)の時間で処理できたので、 最大負荷時の処理性能としても問題ないと判断しました。
関連・参考リンク
ちょこっとアンケート＆メッセージ
このページに関するちょっとした感想または、要望、バグ・間違いの指摘などは、下記の送信欄からお送りください。 質問・その他お問合せなど、返信をご希望の方は「こちらのページ」からメッセージをお送りください。
「このページはお役に立ちましたか？」のアンケートと自由メッセージのどちらか一方でかまいません (両方だとよりうれしいです)。お気軽にご利用ください (感想・どんな用途で使用したかなどをいただけると作成・運営の励みになります！)。
このページはお役に立ちましたか？
画像のひらがな一文字を入力してください。拗音・促音・濁点・半濁点はありません。
※サンプルの追加・ツール改善の参考に利用させていただきます。