競技プログラミングの本を一ヶ月読んでいます。この本は、私たちの国 (バングラデシュ) の世界ファイナリストの 1 人によって書かれています。この本は私たちの母国語 (ベンガル語) で書かれており、世界的にあまり人気がありません。コンテンツがベンガル語であるため、ここでは参照できません。そういうわけで、まず申し訳ありません。
その本の数論の章では、素数性をテストするための多くのアルゴリズムが示されています。彼が示した最も最適なものは、O(nloglogn) の「エラトステネスのふるい」です。しかし、彼は一行書いた。私はそれを翻訳しています。「O(logn) で素数性をテストするより効率的な方法があります。自分で考えてください。元に戻せない場合は、ググってください!!」
私はそれについてグーグルで調べましたが、満足のいくものは見つかりませんでした。
O(logn) で数値の素数をテストすることは本当に可能ですか?? そして、可能であれば、どの範囲まで結論付けることができますか??