• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

Aruba Cloud - Virtual Private Server VPS
+1 głos
1,991 wizyt
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ź

0 głosów
odpowiedź 15 kwietnia 2018 przez mokrowski Mędrzec (158,200 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

Podobne pytania

0 głosów
1 odpowiedź 1,652 wizyt
pytanie zadane 1 lipca 2018 w Algorytmy przez poldeeek Mądrala (5,980 p.)
0 głosów
1 odpowiedź 1,177 wizyt
+1 głos
0 odpowiedzi 511 wizyt

93,335 zapytań

142,330 odpowiedzi

322,416 komentarzy

62,669 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...