Test pierwszości z sitem Etastotenesa

Podsumujmy: to, czy n jest liczbą pierwszą, sprawdzamy metodą próbnych dzieleń. Tu jest pierwiastek kwadratowy z n, a tu jest 3. Zaczynając od trzech, przeskakujemy o dwa pola, aż do pierwiastka z n. Sprawdzamy, czy każda liczba po drodze dzieli n. Do tej pory ludzie starali się zmniejszać liczbę kroków, zaczynając później albo wydłużając te kroki. Zatrzymam się przy tym. Zastanówmy się, jaki jest idealny przypadek dla algorytmu próbnych dzieleń. Co najlepszego możemy w tej sprawie wymyślić? Pamiętajcie, każda liczba n ma rozkład na czynniki pierwsze. Powiedzmy, że tu jest pierwiastek z n. Musimy stawać tylko na liczbach pierwszych. Tak byłoby najlepiej. Zatrzymując się tylko na liczbach pierwszych, w końcu znajdziemy dzielnik n. Pytanie: jak wydajna jest ta metoda? Wydaje się, że mamy doskonałe rozwiązanie. Gdybyśmy napisali nowy algorytm, który najpierw stosowałby sito… Niech oblicza, czy n jest liczbą pierwszą. Jeśli zastosujecie sito i wygenerujecie długą serię liczb pierwszych, a potem zastosujecie metodę próbnych dzieleń… z użyciem tej listy liczb pierwszych… Naszą metodą będziecie przechodzić tylko przez liczby pierwsze. Do pierwiastka z n, jakąkolwiek ma wartość. Co jest z tym nie tak? Możemy wizualizować złożoność czasową albo liczbę wykonanych kroków. Pamiętajcie, wziąłem ten algorytm i dodałem licznik kroków do każdej pętli, więc mamy… Powiedzmy, że „STEP ++” oznacza krok plus jeden. W tej pętli także jest licznik kroków. Step ++. To są stałe operacje, które sprawdzają i oznaczają liczby. W każdej pętli mamy licznik kroków. Teraz porównanie. Po lewej stronie jest metoda próbnych dzieleń, pośrodku algorytm, za pomocą sita generujący wszystkie liczby pierwsze do n, a po prawej jest propozycja, w której stosujemy sito, by generować liczby pierwsze do pierwiastka z n i tylko do nich stosujemy metodę próbnych dzieleń. Zobaczmy, co będzie przy małych danych wejściowych. Jak widzicie, z początku sito zajmuje wiele kroków. Nawet zmodyfikowana wersja po prawej stronie jest wolniejsza od metody próbnych dzieleń. Gdy wprowadzamy większe liczby, liczba kroków rośnie jeszcze szybciej. Zapomnijmy o tym środku i porównajmy metodę próbnych dzieleń z sitem do pierwiastka z n i próbnymi dzieleniami. Zobaczymy, że stara metoda próbnych dzieleń jest znacznie wydajniejsza. Liczba kroków w sicie do pierwiastka z n plus metoda próbnych dzieleń rośnie znacznie szybciej. Zatem to żadne ulepszenie. Poniżej jest program, którego użyłem do tego porównania. Oraz nagranie wyjaśniające, jak to zrobiłem. Pewnie się zastanawiacie: „A gdybyśmy obliczyli liczby pierwsze z wyprzedzeniem?”. Najpierw trzeba byłoby stworzyć tablicę liczb pierwszych i przechowywać ją na twardym dysku. Wtedy nasz algorytm stosowałby tylko metodę próbnych dzieleń, skacząc wyłącznie po liczbach pierwszych, bo korzystałby z listy. Nasz wykaz może zawierać wszystkie liczby pierwsze do 20 cyfr, a nawet do 100. Dlaczego tego nie robimy? Problemem jest ograniczenie pamięci. Sporządzając tabele liczb, czym zajmiemy się później… Powiedzmy, że robimy to ręcznie. Obliczamy, że 5 to liczba pierwsza, zapisujemy piątkę na kartce i przechowujemy w szafce. Później uzyskujemy 7, wkładamy tę liczbę do szafki, 9… przepraszam, 11, do szafki, Uzyskamy szafkę pełną liczb pierwszych. To nasza… tablica liczb pierwszych. Jak duża musiałaby być ta szafka, by pomieścić wszystkie liczby pierwsze do 20 albo 100 cyfr? Czy moglibyśmy przechować taką tabelę na twardym dysku? Żeby zrozumieć, dlaczego nie jest to możliwe, powinniśmy zbadać dokładniej, jak duża musi być tablica liczb pierwszych i jakie jest ograniczenie wielkości współczesnego, a nawet przyszłego sprzętu komputerowego.