Sito Eratostenesa

Co się właśnie stało?

Sito Eratostenesa wypisuje liczby 2, 3, 4, …, N, a potem kolejno wykreśla wielokrotności każdej znalezionej liczby pierwszej — najpierw 2 (4, 6, 8…), potem 3 (6, 9, 12…), potem 5, 7… To, co zostanie niewykreślone, to liczby pierwsze. Prosty, mechaniczny przepis wymyślony ok. 240 r. p.n.e. przez Eratostenesa z Cyreny.

Dlaczego wystarczy przesiewać do $\sqrt{N}$?

Każda liczba złożona $n$ ma dzielnik pierwszy nie większy niż $\sqrt{n}$:

Gdyby oba czynniki były większe od $\sqrt{n}$, ich iloczyn przekroczyłby $n$ — sprzeczność. Dlatego każdą liczbę złożoną wykreśli jakaś liczba pierwsza $p\le\sqrt{N}$ i nie trzeba przesiewać dalej. To klucz efektywności algorytmu.

Liczb pierwszych jest nieskończenie wiele (Euklides, ~300 p.n.e.):

W „Elementach” (Księga IX) Euklides dowodzi tego elegancko przez sprzeczność. Załóżmy, że liczb pierwszych jest skończenie wiele: $p_1, p_2, \ldots, p_k$. Rozważmy liczbę:

Liczba $Q$ nie dzieli się przez żadną z $p_i$ (zawsze zostaje reszta 1). Więc albo $Q$ sama jest pierwsza, albo ma dzielnik pierwszy spoza listy — w obu przypadkach istnieje liczba pierwsza, której nie uwzględniliśmy. Sprzeczność. Zbiór liczb pierwszych jest zatem nieskończony: $|\{p : p \text{ pierwsza}\}| = \infty$.

Rzedną, ale się nie kończą

Wśród kolejnych liczb naturalnych liczby pierwsze pojawiają się coraz rzadziej — ich gęstość $\pi(N)/N$ systematycznie maleje (widać to na pasku po prawej). Mimo to nigdy się nie wyczerpują: zawsze da się znaleźć następną.

Po co Ci to na maturze:

Liczby pierwsze to „cegiełki” wszystkich liczb naturalnych — każda liczba naturalna ma jednoznaczny rozkład na czynniki pierwsze (podstawowe twierdzenie arytmetyki). Sito Eratostenesa i dowód Euklidesa to klasyczne szkolne tematy, a liczby pierwsze są fundamentem współczesnej kryptografii (np. system RSA opiera bezpieczeństwo na trudności rozkładu dużych liczb na czynniki pierwsze).

Zapamiętaj: sito Eratostenesa wykreśla wielokrotności liczb pierwszych aż do $\sqrt{N}$ — bo każda liczba złożona ma dzielnik pierwszy $\le\sqrt{n}$. Liczb pierwszych jest nieskończenie wiele (Euklides), choć ich gęstość maleje.