Najszybszy algorytm odnajdujący liczby pierwsze (Złożoność czasowa log(n))

Question

Witam, mam pytanie! Jaki algorytm do odnajdywania liczb pierwszych do przedziału określonego wartością n można użyć w swoim kodzie? Widziałem Sito Eratostenesa, Sito Atkina, ale nie jestem pewien czy nie ma aby szybszego algorytmu na to. Czytałem, że najszybszą możliwą złożonością czasową jest log(n), czy istnieje taki algorytm odnajdywania liczb pierwszych?

Answer 1

Ok. Sito Atkina Ci nie wystarcza? https://fylux.github.io/2017/03/16/Sieve-Of-Atkin/ Bernstein na swojej stronie umieścił prace i implementację.

Ogólnie im więcej pamięci poświęcisz, tym mniejszą złożoność obliczeń uzyskasz.

Tu masz jeszcze inną pracę na temat generowania liczb pierwszych (taka mikro-przegłądówka). Ogólne pytanie brzmi jak mocno jesteś zdeterminowany by w problem wchodzić? https://pdfs.semanticscholar.org/eaae/76a16ace5ddcab098a5be5070fedfa48e707.pdf