Liczby pierwsze

Liczby pierwsze

Definicja: Liczbę naturalną p, która ma dokładnie dwa różne dzielniki (1 i p), nazywamy liczbą pierwszą.

Jak wyznaczyć wszystkie liczby pierwsze nie większe niż N?

Efektywną metodę podał Eratostenes, chciał bowiem stworzyć tablicę liczb pierwszych. W tym celu na drewnianej tablicy wypisał liczby: 2, 3, ..., N. Wziął pod uwagę pierwszą z liczb i wykreślił wszystkie jej wielokrotności. Najmniejsza niewykreślona liczba to 3. Zatem 3 jest liczbą pierwszą. Następnie wykreślił wszystkie liczby podzielne przez 3 itd. W ten sposób Eratostenes wyznaczał kolejne liczby pierwsze. Aby sprawdzić, czy dana liczba N jest pierwsza, należy wyznaczyć wszystkie liczby pierwsze i sprawdzić, czy dzielą one N. Jeżeli nie, to N jest pierwsza. Algorytm ten często nosi nazwę sito Eratostenesa. Nazwa wzięła się stąd, że Eratostenes faktycznie nie skreślał liczb, ale wycinał pod nimi dziury przypuszczając, iż liczby te wypadły przez zrobione otwory i tym sposobem na tablicy (jak na sicie) pozostały tylko liczy pierwsze.

Liczbami pierwszymi zajmowano się również później. Wielu uczonych próbowało znaleźć wzór który opisywałby liczby pierwsze.

Leonhard Euler (1707-1783) podał następujące wzory:
1. dla x = 0, 1, ..., 39
2. dla x = 0, 1, ..., 28

Andrien Marie Legendre (1752-1833) podał wzór: dla x = 0, 1, ..., 16

Marin Mersenne podał wzór dla liczb pierwszych: gdzie p jest liczbą pierwszą.

Obecnie wiadomo, że największa znaleziona liczba pierwsza ma 227823 cyfr, a jej zapis zajmuje 32 kartki papieru formatu A4.