Zaczynam nauke algorytmow i ostatnia poznalem rozne metody wygenerowania liczb pierwszyc, a dokladniej sito Erastotenesa, sito liniowe, sito Atkina Bernsteina. Moglby mi ktos odpowiedziec ktorego najlepiej uzywac ?
Wiem ze na internecie mozna znalezc zlozonosc tych algorytmow, ale nie jestem jeszcze na takim poziomie matematycznym zeby moc porownac ktora jest lepsza.
0
2
Sito Eratostenesa:
Proste do napisania - to jego główna zaleta. Wynika z tego też że można go napisać szybko i łatwo zapamiętać, z tego powodu na przykład łatwo zastosować na jakimś konkursie algorytmicznym.
Wadą jest to że jest wolne - O(n log log n) ( ) - chociaż można to poprawić.
Dodatkowo zajmuje dużo pamięci - O(n) ( ) - czyli liniowo w stosunku do ilości liczb (to też można znacząco poprawić zmieniając trochę algorytm).
Sito Atkina:
Zdecydowanie trudniejsze do napisania i zrozumienia, szczególnie z pamięci.
Szybsze od Eratostenesa - O(n / (log log n)) ( ) - chociaż ma większy czynnik stały - co oznacza że dla małych wartości górnych, szybszy będzie i tak Eratostenes.
I zajmuje mniej pamięci - blisko O(sqrt(n)) ( )
Ogólnie 'lepsze' (szybsze) jest sito Atkina, ale jeśli potrzebujesz coś na szybko napisać i niekoniecznie potrzebujesz działać na olbrzymich liczbach, Eratostenes jest prostą alternatywą.
Jeśli piszesz program 'użytkowy':
- jeśli wiesz że będziesz potrzebował tylko niezbyt dużych liczb pierwszych - na przykład do 1000, nie ma co się zastanawiać nad Atkinem.
- jeśli wiesz że będziesz potrzebował dużych liczb pierwszych... warto pomyśleć nad implementacją sita Atkina, chociaż jeszcze lepiej byłoby znaleźć gotową bibliotekę implementującą szybki algorytm szukania liczb pierwszych (skoro ktoś to już napisał to po co się męczyć?)
Jeśli bierzesz udział w jakimś konkursie algorytmicznym:
- jeśli piszesz go na spokojnie w domu - optymalizuj co się da, Atkin Twoim przyjacielem
- jeśli piszesz go 'na żywo', mając kilka godzin na zrobienie wszystkich zadań - też możesz użyć - jeśli zdążysz i znasz na pamięć.