Wstęp

W książce"Liczby pierwsze - w drodze do nieskończoności" Enrique Graciana możemy przeczytać wspaniały fragment dotyczący liczb pierwszych. Przeczytajmy:

     "Można powiedzieć, że w arytmetyce większość liczb zachowuje się porządnie. Liczby parzyste występują naprzemian z nieparzystymi, co trzecia liczba musi być wielokrotnością liczby 3, kwadraty liczby podlegają łatwej do wprowadzenia regule. [...] Natomiast liczby pierwsze to niesforna zgraja. Pojawiają się tam, gdzie chcą, bez ostrzeżenia, w sposób pozornie chaotyczny, bez żadnych reguł. A najgorsze, że nie da się ich ignorować - są absolutnie niezbędne w arytmetyce i całej matematyce."

Liczby pierwsze są absolutnie zadziwiające mimo swej prostoty. Rzadko sobie uświadamiamy, że mamy z nimi do czynienia wszędzie, a szczególnie jeśli dotyczy do ochrony danych - kart bankowych, systemów bezpieczeństwa komputerów czy ochrony prywatności rozmów mailowych czy telefonicznych. Jeden z nowoczesnych systemów kryptograficznych KRYPTOSYSTEM RSA opiera się właśnie na operacjach z wykorzystaniem liczb pierwszych.

Wszyscy najwięksi matematycy jak Euklides, Fermat, Euler czy Gauss i wielu, wielu innych byli zafascynowani liczbami pierwszymi i wiele lat swego życia poświęcili na badanie ich zależności i swoistej "magii".

Definicja

Liczby pierwsze nie są żadnym skomplikowanym pojęciem. Wystarczy znać podstawowe operacje matematyczne i pojęcie zbioru liczb naturalnych, które są całkowite i dodatnie. Zapoznajmy się więc z definicją liczb pierwszych.

Liczby pierwsze

Jak znaleźć liczby pierwsze?

Jeśli chcemy stwierdzić czy dana liczba jest pierwsza, to najprościej można sprawdzić czy liczba ta nie dzieli się przez liczby naturalne mniejsze do niej, np:

chcemy stwierdzić czy liczba 13 jest liczbą pierwszą. Sprawdzamy czy liczba ta nie dzieli się przez 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Liczba 13 nie dzieli się przez żadną z tych liczb, więc jest liczbą pierwszą. Oczywiście sposób jest prosty w swojej logice, ale przy większych liczbach żmudny, a przy bardzo wielkich wręcz niemożliwy do zastosowania.

Testy pierwszeństwa

Samotna liczba 2 - jedyna taka pierwsza

Oczywiście pewne liczby możemy od razy odrzucić, bo łatwo stwierdzimy, że nie są to liczby pierwsze.

Pierwszy test to liczby parzyste. Zauważmy, że jedyną liczbą pierwszą, która jest parzysta jest liczba 2. Wszystkie pozostałe liczby parzyste na pewno dzielą się przez 2, więc nie są pierwsze. Oczywiście to pierwszy z prostych testów, który możemy zrobić. Potem możemy usuwać liczby podzielne przez 3, 5 itd.

Sito Eratostenesa

Generowanie liczb pierwszych zawsze było jakimś jednak problemem ze względu na czasochłonność. Jedna z pierwszych metod jest przypisywana Eratostenesowi z Cyreny (275-194 p.n.e). Był to matematyk grecki zajmujący się również geografią i astronomią. Motodę nazywamy sitem Eratostenesa, ponieważ polega na swoistym przesiewaniu liczb, które na pewno nie są pierwsze na dany moment sprawdzania od potencjalnie nadal pierwszych.

Eratostenes

Sito Eratostenesa - liczby pierwsze mniejsze od 100

Zadanie

Spróbuj za pomocą sita Eratostenesa wyznaczyć liczby z przedziału 100 - 200, a następnie sprawdź swoje wyniki z tabelą liczb pierwszych mniejszych od tysiąca na planszy poniżej.