➗Testowanie liczb pierwszych

Czym są liczby pierwsze

Liczba pierwsza to liczba całkowita równa 2 lub większa, której jedynymi dzielnikami są 1 i ona sama. Liczby 2, 3, 5, 7, 11 to liczby pierwsze, a 2 jest jedyną parzystą liczbą pierwszą.

Czy 1 jest liczbą pierwszą?

Nie, 1 nie jest liczbą pierwszą. Liczby pierwsze są definiowane jako liczby całkowite równe 2 lub większe. Jeśli włączyć 1 do liczb pierwszych, podstawowa właściwość rozkładu na czynniki pierwsze (każdą liczbę całkowitą można wyrazić jako iloczyn liczb pierwszych na dokładnie jeden sposób) przestałaby być prawdziwa.

Jak rozpoznać liczby pierwsze

Aby sprawdzić, czy liczba całkowita n jest pierwsza, podziel ją kolejno przez liczby do √n. Jeśli żaden z nich nie dzieli się równo, liczba jest pierwsza. Na przykład 91 nie jest pierwsze, ponieważ dzieli się przez 7, które jest mniejsze niż √91 (około 9,5).

• Metoda dzielenia próbnego：Metoda dzielenia próbnego polega na dzieleniu liczby n przez kolejne liczby od 2 do √n w celu znalezienia dzielników. Dla dużych liczb wymaga to ogromnej liczby dzieleń.
• Test Millera-Rabina：Test Millera-Rabina sprawdza reszty z potęg, używając kilku liczb jako podstaw, aby znaleźć dowód na to, że liczba nie jest pierwsza. Ta metoda sprawdza się szybko nawet dla dużych liczb.