素数の生成アルゴリズムについてです。

質問

下記リンク内のアルゴリズムでは、多項式時間内に素数の生成が可能でしょうか。
なお、同スレ内には、他にも多々、素数生成アルゴリズムをコレクションしてありますので、出来ましたら、それらの時間計算量につきましても御教え下さい。

https://twitter.com/koitiluv1842/status/1500429851630931970

回答No.1

f272 · ベストアンサー

Finding Primes using a Parabolaと書いてあるアルゴリズムでしょうか？
それならエラトステネスの篩と同じです。多項式時間内に素数の生成が可能です。

お礼

早速の御回答を誠に有難う御座いました。

補足

なお、上掲リンク内のスレには、小林吹代、菅野正人、故・川村甲子郎の各氏や、海外の研究者による、素数生成アルゴリズム・素数生成公式も集めましたので、それも併せて御検討くださいますでしょうか。
（スレ内の全ツイートを御高覧いただくには、全ツイート年月日をクリックして下さい。ツイッター社が、多数のツイートを隠してしまっていますので。）