Sito Eratostenesa

Przedstawię teraz starożytną metodę generowania listy liczb pierwszych do jakiejś granicy n, znaną jako Sito Eratostenesa. Eratostenes urodził się w 276 r. p. n. e. Metoda ma więc ponad 2200 lat. Jest bardzo prosta i elegancka. Można jej nauczyć każde dziecko. Powiedzmy np., że chcemy obliczyć wszystkie liczby pierwsze do 100. Działałoby to tak samo, gdybyśmy chcieli wyznaczyć te liczby do 10 000 lub miliarda. Robi się tak: najpierw wszystkie liczby są niezaznaczone. Szare tło. Zaczynamy od początku. Trafiamy na liczbę niezaznaczoną: jest to liczba pierwsza. Trafiamy na 2 i mówimy: to liczba pierwsza, bo niezaznaczona. W drugiej fazie eliminujemy wszystkie wielokrotności dwóch, bo wiemy, że to liczby złożone. Bum! Eliminujemy wszystkie wielokrotności dwóch. Czerwień oznacza liczbę złożoną. I powtarzamy. Przechodzimy do liczby 3. Jest niezaznaczona, czyli to liczba pierwsza. I eliminujemy wielokrotności trzech. Proste ulepszenie: zauważcie, że szóstka jest już wykreślona. Zaczynamy eliminować wielokrotności od kwadratu tej liczby. 3 razy 3 to 9. Zaczynamy od 9 i zaznaczamy wszystkie wielokrotności 3 jako liczby złożone. Wracamy. Trafiamy na 4. Zaznaczone – czyli to liczba złożona. Przeskakujemy do piątki. Niezaznaczona. Liczba pierwsza. 5 razy 5 to 25, idziemy do tego pola. Oznaczamy 25, 30, 35, 40, 45 itd. To liczby złożone. Idziemy dalej. 7. Wiemy, że to liczba pierwsza, bo nie została zaznaczona. 7 razy 7 to 49, oznaczamy tę i resztę wielokrotności 7 powyżej. Złożone. Idziemy dalej. Trafiamy na 11: to liczba pierwsza. Zauważcie: 11 razy 11 jest większe niż 100, więc możemy się tu zatrzymać. Moglibyśmy się zatrzymać przy 10, bo wszystkie pozostałe niezaznaczone liczby są pierwsze. Za jednym zamachem możemy je zaznaczyć jako pierwsze. I to cały algorytm. Taki prosty. Uogólnijmy to teraz, żeby napisać program do wykonania sita. Chcąc wyznaczyć liczby pierwsze do danej granicy n, najpierw stwórzmy główną pętlę. Dla wszystkich a, od 2 do pierwiastka z n. Zauważcie: zatrzymaliśmy się przy 10; pokazałem to przy 11. Znaleźliśmy wszystkie liczby pierwsze. Od dwóch do pierwiastka kwadratowego z n robimy tak: jeśli a jest niezaznaczone… to wiemy, że jest liczbą pierwszą, a kiedy znajdziemy liczbę pierwszą, zaznaczymy wszystkie wielokrotności a jako liczby złożone. I już. Znajdujecie liczbę pierwszą, zaznaczacie wielokrotności, wracacie na początek, zwiększacie a o 1… Jesteśmy przy 2, przechodzimy do 3, potem do 4, 5 itd. A kiedy skończymy, będziemy mieć wszystkie liczby pierwsze. Zauważcie, że to także jest pętla. Mamy główną pętlę na wypadek znalezienia liczby pierwszej, ale to odznaczanie wielokrotności także jest pętlą. Zauważcie, że mamy zagnieżdżoną pętlę: pętlę w pętli. To jest przykład takiego algorytmu. Napisałem go w języku JavaScript. Wprowadzam 100. Tu będą wszystkie liczby pierwsze mniejsze od 100. Wprowadzam 200 i mam wszystkie liczby pierwsze do 200. A jeśli wprowadzę 850… To będą wszystkie liczby pierwsze do 850. Poniżej mam ten program z nagraniem, które objaśnia, jak to zrobiłem.