Logowanie

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

pytanie zadane 15 kwietnia 2018 w Algorytmy przez Kamil Paradowski Użytkownik (620 p.)

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?

1 odpowiedź

odpowiedź 15 kwietnia 2018 przez mokrowski Mędrzec (158,940 p.)

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