Sito Eratostenesa

Jak prosto znaleźć wszystkie liczby pierwsze w zadanym przedziale metodą znaną jako Sito Eratostenesa.

Wstęp

Często spotykamy się z problemem znalezienia w danym przedziale wszystkich liczb pierwszych. Można to łatwo zrobić sprawdzając po kolei każdą z nich, czy jest złożona. Rozwiązanie to jednak nie byłoby efektywne. Jest inna, szybsza metoda rozwiązanie tego problemu. Jest to tzw. "sito Eratostenesa". Nazwa pochodzi od tego, że wszystkie liczby są po kolei przesiewane i usuwane są wszystkie wielokrotności danej liczby. Żeby wszystko stało się jaśniejsze przejdźmy do przykładu.

Przykład

Znajdźmy na przykład wszystkie liczby pierwsze od 1 do 20. Liczby złożone będą po kolei "usuwane" w sposób podany niżej. Na początku nasz przedział wygląda następująco:

Cała idea tego algorytmu polega na tym, że "idziemy" od lewej strony przedziału poczynając od liczby 2 i gdy liczba ta nie została wcześniej skreślona to skreślamy wszystkie jej wielokrotności w danym przedziale oprócz niej samej.

Tak więc zaczynamy od liczby 2. Nie jest ona skreślona, więc skreślamy jej wielokrotności oprócz niej samej. W tym przypadku są to liczby: 4, 6, 8, 10, 12, 14, 16, 18, 20.

Po skreśleniu (usunięciu) wyżej wymienionych liczb otrzymujemy:

Kolejną liczbę, jaką napotykamy po 2 jest liczba 3. Nie została ona wcześniej skreślona, więc skreślamy wszystkie jej wielokrotności w naszym przedziale od 1 do 20 oprócz niej samej. Proszę zauważyć, iż niektóre wielokrotności liczby 3 zostały już skreślone wcześniej. Liczby, które w tym przypadku skreślimy to: 6, 9, 12, 15, 18. Po tej operacji otrzymamy:

Kolejną liczbę, jaką napotkamy idąc od lewej to 4. Ponieważ została ona już wcześniej skreślona to nie wykonujemy już żadnych dodatkowych skreśleń.

Proszę zauważyć, że w naszym przedziale zostały już tylko liczby pierwsze. Musimy jeszcze skreślić liczbę 1:

W sicie Eratostenesa może pojawić się jeden problem - a mianowicie do której liczby mamy dojść idąc od lewej od liczby 2, aby w danym przedziale zostały nam tylko liczby pierwsze? Moja odpowiedź brzmi do zaokrąglonego w dół pierwiastka kwadratowego największej liczby z danego przedziału. W naszym przypadku największą liczbą jest 20. Pierwiastek kwadratowy z 20 to około 4,47. Gdy zaokrąglimy tą liczbę w dół to otrzymamy 4. I tylko do tej liczby doszedłem w przykładzie powyżej. Teraz postaram się wytłumaczyć, dlaczego akurat dochodzimy do tej liczby. Każda liczba złożona w danym przedziale to iloczyn dwóch innych liczb (nie muszą być one koniecznie pierwsze). Liczby te mogą być równe sobie - wtedy wartość tych liczb to pierwiastek kwadratowy z danej liczby złożonej. Jednakże, gdy liczby te nie są sobie równe - to jedna jest większa, a druga mniejsza. Mniejsza z tych liczb jest mniejsza od pierwiastka kwadratowego z danej liczby złożonej. Tak więc, aby skreślić daną liczbę złożoną musimy dojść (gdy idziemy po kolei od 2) do tej mniejszej liczby, nie musimy wcale dochodzić do tej większej.