Sito Eratostenesa

jest znane od 23 stuleci. Umożliwia ono znajdywanie L. pierwszych w zadanym zakresie. Natomiast w przeciwieństwie do E-sita, używając ciągów Dirichleta – możemy je ciągnąć w nieskończoność (oczywiście: dopóki nam nie wyłączą prądu ;-) ). Z drugiej jednak strony ciągi te (prócz najbardziej obszernego) nie dają nam ani wszystkich liczb pierwszych, ani nawet – samych takich liczb. Bowiem znaczna część wyrazów – okazuje się być L. złożonymi…

Przyjrzyjmy się dokładniej tej klasycznej metodzie. Okazuje się, że dla zapisania nawet gigantycznych liczb – wcale nie potrzeba tak dużo pamięci! Bowiem aby prowadzić ich selekcję, to przy sprytnie użytej metodzie ich reprezentacji, i pomysłowym rozmieszczeniu w tablicy – dla „zapamiętania” każdej z badanych, choćby i największej, kilkusetcyfrowej liczby, wystarczy… jeden, jedyny, pojedynczy bit!

Inaczej niż przedstawione przeze mnie rzeszoto, E-sito wskazuje L. pierwsze całkowicie nieomylnie: jeśli wszystkie operacje przeprowadziliśmy prawidłowo (no cóż, zazwyczaj zlecamy to maszynie, a więc trzeba napisać: jeśli w kodzie nie ma błędów…), to wskazywane obiekty są niezawodnie L. pierwszymi.

Jednak – i do tego właśnie zmierzałem – sito wymaga podania górnego zakresu przeszukiwanych liczb, co nie zawsze możemy uczynić, jeśli zagadnienie, dla rozwiązania którego poszukujemy danej liczby – nic nie mówi o jej wielkości. A przecież tak czasem bywa! Np. wiemy tylko to, że szukana liczba ma mieć na trzecim od końca miejscu cyfrę 6, a na 4-tym 8-kę, itp.

Lecz przecież można kod dla E-sita napisać tak, że po przeszukaniu wskazanego wstępnie obszaru do liczby a₁, jeśli zajdzie potrzeba, maszyna może tabelę znalezionych liczb pierwszych kompresować do mniejszych rozmiarów (zapamiętując jedynie odpowiednie wartości), po czym o zadaną wartość „sziftować” pole badań, czyścić je, a potem będzie przeczesywać kolejne zakresy. Np. od a₁ do a₂ – gdzie może być  2_*a₁ = a₂   – następnie od a₂ do a₃ (=3_*a₁) – korzystając przy tym z danych (tablica znalezionych L.p.) uzyskanych w poprzednich sesjach, etc. etc…

Stopień złożoności wzrośnie dość nieznacznie, natomiast użyteczność programu – zwielokrotni się! Niewielka, dodatkowa komplikacja polegać będzie na konieczności prawidłowego wyznaczania każdorazowych „miejsc startowych” dla wykreślania (false) kolejnych pozycji w tabeli, która będzie wielokrotnie „sziftowana” – czyli przesunięta o dużą liczbę. Lecz przecież dla każdej, danej L. pierwszej p, której wielokrotności właśnie z badanego zakresu liczb chcemy wykreślić (odrzucić), wystarczy znaleźć resztę z dzielenia mod(„wartość Shift-u" ; p ), i… już mamy (ujemną) wartość pozycji w tabeli, PRZED którą należy zacząć wykreślanie.

Oczywiście dla przechowywania L. pierwszych „już znalezionych” – w poprzednich nawrotach – musimy wówczas stworzyć osobną tablicę, w dodatku o rozmiarach określanych dynamicznie. Zapewne i tu przyda się kilka sztuczek, w rodzaju powyższych, aby oszczędzać pamięć maszyny…

Reasumując: sito Eratostenesa jest narzędziem w 100 % niezawodnym, a jak się okazuje, gdy je zaimplementujemy w sposób odpowiednio pomysłowy, może być też zaskakująco wydajnym. No tak, oczywiście, trudno wymyślić coś nowego, jeśli dany temat penetrowali już antyczni Grecy…  Strach pomyśleć, czego by nie narobili, gdyby mieli… komputery i internet!! Dla nas nie zostało by już chyba nic…