素数生成機

素数リストの生成


区切り文字 範囲サンプル
Result:

次の素数は?

入力された数字次の素数を表示します。

桁の ※「任意の整数」を入れるのが面倒なときに使う

概要

「素数の生成」を行えるツール、「素数ジェネレーター」です。

「素数リストの生成」は、指定数以下の素数をリストアップします。1000万以下の数値に対応しています。

「次の素数は?」は、入力された自然数の次の素数を見つけます。500桁以下の数値に対応しています。

※「処理時間」は、JavaScript内部で素数リスト配列を作成し終わるまでの時間を表示しています。 素数リスト配列をカンマ区切りの文字列などに整形しますが、その時間は含んでいません。

補足

コメント

「素数リストの生成」のアルゴリズムは、Wikipediaの「エラトステネスの篩」の説明を忠実に実装しました。最初は。 しかし、パフォーマンスのよい優れた実装「エラトステネスの篩を書いてみた - Qiita」を見つけたため、拝借させていただきました。

「処理時間」は、素数リストの生成に要した時間です。 1000万など大きい数を指定すると、「処理時間」より明らかに長く時間がかかりますが、 それは素数リストを生成し終わったあとの表示処理に時間がかかっているためです。

「素数リストの生成」は処理上限を1000万としています。この値は、 私のPC(Win7 64bit, Corei7, RAM 8GB)で処理できるかどうかを基準に決めました。 PCでは851msec、Nexus7(Android5.0.2, RAM 1.8GMB)では3394msecで処理でき、 古いスマホ(Android4.0.3, RAM 660MB)ではエラーになりました。 古い・性能の低いPC・スマホでは、動作は保証できません。

「次の素数は?」は、PHPのgmp_nextprime関数を使用しています。その説明に 「この関数は素数を識別するのに確率的アルゴリズムを使用します。 誤って合成数を取得してしまうことは、まずありません。」 とあります。一応それを信じます。

「素数リストの生成」は、十分なテストを行ったとはいえません。 しかし、「素数リストの生成」では100万以下・1000万以下の素数の数が正しかったことから、一応問題ないと判断しました。 もし不具合があったら教えてください。

関連・参考リンク

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

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

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


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