• 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))

Object Storage Arubacloud
+1 głos
1,695 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 (156,220 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,442 wizyt
pytanie zadane 1 lipca 2018 w Algorytmy przez poldeeek Mądrala (5,980 p.)
0 głosów
1 odpowiedź 944 wizyt
+1 głos
0 odpowiedzi 343 wizyt

92,677 zapytań

141,581 odpowiedzi

320,061 komentarzy

62,039 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.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...