Liczbą pierwszą jest liczba, która ma tylko 2 dzielniki naturalne: 1 i siebie samą.
Liczby pierwsze do 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Liczby, ktore nie są liczbami pierwszymi to liczby złozone, czyli takie, które mają więcej niż 2 dzielniki naturalne, z czego wynika, że można je przedstawić jako iloczyn dwuch liczb całkowitych większych od 1.
Wyjątkami są liczby 0 i 1, które zarówno nie są liczbami pierwszymi (0 ma nieskączoność dzielników, a 1 tylko 1), jak i trudno je nazwać liczbami złożonymi.
Mozna znaleźć jej wszystkie dzielniki naturalne. Jeśli znajdziemy 2 dzielniki to jest to liczba pierwsza, ale można dowiedzieć się tego szybciej.
Zauważmy, że jak p dzieli liczbę n to \(\frac{n}{p}\) też dzieli n.
$$n = p*x$$
$$n = \frac{n}{p}*p$$
Czyli każdy dzielnik oprucz pierwiastka z danej liczby (w 4 odpowiednik 2 to też 2) ma swój odpowiednik (np. przy 12: 1 -> 12, 2 -> 6, 3 -> 4, 4 -> 3, 6 -> 2, 12 -> 1).
Policzmy kiedy \(p \le \frac{n}{p}\):
$$p \le \frac{n}{p}$$
$$p^2 \le n$$
$$p \le \sqrt{n}$$
Czyli wystarczy znaleźć wszystkie dzielniki naturalne \(\le \sqrt{n}\), żeby wiedzieć czy liczba jest liczbą pierwszą
Przykłady:
Sprawdź czy 17 to liczba pierwsza:
\(\sqrt{17} = 4,123...\) więc wystarczy znaleźć wszystkie dzielniki naturalne 17 \(\le 4\). Jest to jedynie 1, więc 17 to liczba pierwsza.
Sprawdź czy 42 to liczba pierwsza:
\(\sqrt{42} = 6,480...\) więc wystarczy znaleźć wszystkie dzielniki naturalne 42 \(\le 6\). Są to: 1, 2, 3 i 7, więc 42 to liczba złożona.
Sprawdź czy 53 to liczba pierwsza:
\(\sqrt{53} = 7,280...\) więc wystarczy znaleźć wszystkie dzielniki naturalne 53 \(\le 7\). Jest to tylko 1, więc 53 to liczba pierwsza.
Sprawdź czy 63 to liczba pierwsza:
\(\sqrt{63} = 7,937...\) więc wystarczy znaleźć wszystkie dzielniki naturalne 63 \(\le 7\). Są to 1 i 3, więc 63 to liczba złożona.
Innymi słowy wystarczy znaleźć jakiś dzielnik liczby n większy niż 1, ale mniejszy niż \(\sqrt{n}\), by powiedzieć, że n to liczba złożona.
Wystarczy, że nie ma dzielników liczby n większy niż 1, ale mniejszy niż \(\sqrt{n}\), by powiedzieć, że n to liczba pierwsza.