素数生成機

素数リストの生成

以下の
区切り文字
Result:

次の素数は?

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

概要

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

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

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

補足

コメント

「素数リストの生成」のアルゴリズムは、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万以下の素数の数が正しかったことから、一応問題ないと判断しました。 もし不具合があったら教えてください。

関連

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

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

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


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