Jak Używać
- Wprowadź dane
Wpisz wymagane wartości w pola wejściowe.
- Dostosuj ustawienia
Wybierz odpowiednie opcje i ustawienia.
- Zobacz wyniki
Kliknij Oblicz aby uzyskać natychmiastowe wyniki.
Czym jest liczba pierwsza?
Liczba pierwsza (prime number) to liczba naturalna większa od 1, której jedynymi dzielnikami są 1 i ona sama. Liczby mające dokładnie dwa dzielniki, takie jak 2, 3, 5, 7, 11 i 13, są pierwsze, natomiast 4, 6, 8 i 9, mające trzy lub więcej dzielników, zaliczane są do liczb złożonych.
Liczby pierwsze są niczym 'atomy mnożenia', z których zbudowana jest każda liczba naturalna. Zgodnie z podstawowym twierdzeniem arytmetyki każdą liczbę naturalną większą od 1 można rozłożyć na iloczyn liczb pierwszych na dokładnie jeden sposób.
Dlaczego to ważne
- Kryptografia: bezpieczeństwo szyfrowania z kluczem publicznym RSA opiera się na trudności ponownego rozłożenia iloczynu dwóch dużych liczb pierwszych na czynniki.
- Skracanie ułamków: znajomość czynników pierwszych licznika i mianownika pozwala z łatwością skrócić ułamek do postaci nieskracalnej.
- Teoria liczb: liczb pierwszych jest nieskończenie wiele (dowód Euklidesa), ale ich rozmieszczenie wciąż pozostaje jednym z wielkich nierozwiązanych problemów.
Wzór obliczeniowy
Ten tester stosuje dzielenie próbne (trial division) z optymalizacją 6k±1. Jeśli n jest liczbą złożoną, jeden z jej dzielników musi być nie większy niż √n, dlatego po wstępnym odsianiu przez 2 i 3 sprawdza tylko i oraz i+2 począwszy od 5, dopóki i*i ≤ n.
Kluczowe warunki: n < 2 → nie jest liczbą pierwszą, a jeśli n % i === 0 okaże się prawdziwe choć raz, liczba jest złożona.
Na przykład, ponieważ √97 ≈ 9,85, wystarczy spróbować podzielić 97 przez 2, 3, 5 i 7. Żadna z nich nie dzieli jej bez reszty, więc 97 jest liczbą pierwszą. Natomiast 91 daje 91 ÷ 7 = 13, czyli 91 = 7 × 13 jest liczbą złożoną.
Rozkład na czynniki pierwsze polega na kolejnym dzieleniu przez najmniejsze liczby pierwsze, grupując powtarzające się czynniki w postaci potęg. Przykład: 360 = 2³ × 3² × 5.