Kalkulator liczb pierwszych

Kalkulator liczb pierwszych

Liczba pierwsza dzieli się bez reszty tylko przez 1 i samą siebie. Wszystkie pozostałe liczby całkowite większe od 1 są złożone i można je rozłożyć na czynniki pierwsze.

Jak sprawdzamy pierwszość?

Wystarczy testować dzielniki od 2 do pierwiastka z badanej liczby. Jeśli żaden nie dzieli jej bez reszty — liczba jest pierwsza. Metoda jest szybka nawet dla dużych wartości.

Przykład

Liczba 360 jest złożona: 360 = 2 × 2 × 2 × 3 × 3 × 5, czyli 2³ × 3² × 5. Ma 24 dzielniki. Najbliższa mniejsza liczba pierwsza to 359, a większa — 367.

Zastosowania

• Szyfrowanie RSA opiera się na dużych liczbach pierwszych.
• Rozkład na czynniki przydaje się przy skracaniu ułamków i NWD.
• Generatory liczb losowych i funkcje skrótu (hash).

Jak działa kalkulator krok po kroku

Kalkulator przyjmuje jedną liczbę całkowitą i najpierw sprawdza, czy w ogóle ma sens badanie jej pierwszości. Dla wartości mniejszych od 2 narzędzie kończy analizę od razu, bo pierwszość definiuje się wyłącznie dla liczb większych od 1. Dla liczby 2 lub większej uruchamiany jest test dzielników, choć dla 2 i 3 zakres może być pusty, ponieważ pierwiastek jest mniejszy od 2. Narzędzie nie korzysta z gotowej tablicy stałych, więc nie zakłada z góry żadnej listy liczb pierwszych — wszystko liczy na bieżąco dla wprowadzonej wartości.

Test polega na sprawdzaniu kolejnych dzielników całkowitych od 2 do pierwiastka z badanej liczby. Jeśli którykolwiek dzielnik dzieli liczbę bez reszty, wynik jest przesądzony: liczba jest złożona. Jeśli zakres zostanie wyczerpany i żaden dzielnik nie pasuje, liczba jest pierwsza. Taki skrót wynika z prostej zależności: gdy n = a × b i a ≤ b, to a nie może być większe niż pierwiastek z n. Sprawdzanie większych potencjalnych dzielników jest więc zbędne i tylko wydłużałoby obliczenia.

Przy rozkładzie na czynniki narzędzie szuka najmniejszego dzielnika większego od 1, dzieli przez niego liczbę, a potem powtarza operację na ilorazie. Czynniki są zbierane do momentu, gdy iloraz osiągnie 1. Dzięki temu powstaje zapis w postaci iloczynu liczb pierwszych, a z wykładników można policzyć liczbę dzielników. Dla liczby pierwszej rozkład kończy się na niej samej, bo nie ma mniejszych czynników całkowitych większych od 1. Cały mechanizm jest deterministyczny: dla tej samej liczby zawsze daje ten sam wynik.

Przykład krok po kroku: liczba 24

1. Ustalenie zakresu. Badamy liczbę 24. Pierwiastek z 24 wynosi około 4,89, więc wystarczy testować dzielniki całkowite od 2 do 4. Liczby większe od 4 nie mogą być mniejszym czynnikiem w żadnym rozkładzie 24.
2. Test dzielnika 2. 24 dzielimy przez 2: 24 / 2 = 12, reszta 0. To oznacza, że 24 nie jest liczbą pierwszą — jest złożona. Do samego stwierdzenia złożoności można przerwać test, bo znalezienie jednego dzielnika wystarcza.
3. Kontynuacja rozkładu. Skoro 2 dzieli 24, zapisujemy czynnik 2 i przechodzimy do ilorazu 12. Ponownie dzielimy przez 2: 12 / 2 = 6, więc dopisujemy drugi czynnik 2.
4. Kolejny krok. Iloraz 6 dzielimy przez 2: 6 / 2 = 3. Mamy trzeci czynnik 2. Teraz zostaje liczba 3, która nie dzieli się przez 2.
5. Zamknięcie rozkładu. Liczba 3 dzieli się przez 3: 3 / 3 = 1. Dopisujemy czynnik 3. Ostatecznie 24 = 2 × 2 × 2 × 3, czyli 2³ × 3.
6. Wynik i liczba dzielników. Z wykładników 3 i 1 obliczamy liczbę dzielników: (3 + 1) × (1 + 1) = 4 × 2 = 8. Dzielniki 24 to 1, 2, 3, 4, 6, 8, 12 i 24. To potwierdza, że 24 ma więcej niż dwa dzielniki, więc jest złożona.

Tabela referencyjna testu dzielników

Praktyczne wskazówki

• Wpisuj liczbę całkowitą bez separatorów. Nie dodawaj spacji, kropek ani przecinków w środku liczby, bo kalkulator może odczytać je jako znak niecyfrowy. Dla wartości ujemnych i zera sprawdzenie pierwszości nie ma zastosowania.
• Zacznij od małych dzielników. Ręcznie najszybciej sprawdzisz 2, 3 i 5. Jeśli liczba kończy się na 0, 2, 4, 6 lub 8, jest parzysta i większa od 2, więc od razu wiadomo, że nie jest pierwsza.
• Pamiętaj o pierwiastku. Dla 360 wystarczy zakres do 18, a dla 24 do 4. Nie ma potrzeby liczyć dalej, jeśli szukasz tylko potwierdzenia pierwszości lub pierwszego dzielnika.
• Wykorzystaj rozkład do porównań. Mając czynniki pierwsze, łatwiej ustalić wspólne elementy dwóch liczb, uprościć zapis i policzyć liczbę dzielników z wykładników.
• Sprawdzaj kilka sąsiednich wartości. Pojedynczy wynik nie pokazuje rozkładu liczb pierwszych w przedziale. Wpisz kilka kolejnych liczb, aby zobaczyć, że w miarę wzrostu wartości przerwy między nimi bywają różne.

Ograniczenia i założenia

• To test próbnego dzielenia. Narzędzie nie używa tablic stałych ani probabilistycznych testów pierwszości. Dla bardzo dużych liczb zakres sprawdzeń rośnie do pierwiastka, więc obliczenia mogą trwać zauważalnie dłużej.
• Nie zastępuje kryptografii. Choć liczby pierwsze mają znaczenie w specjalistycznych zastosowaniach, ten kalkulator służy do nauki i szybkich sprawdzeń. Nie generuje kluczy ani nie zapewnia bezpieczeństwa kryptograficznego.
• Nie obsługuje liczb spoza zbioru całkowitych. Ułamki, liczby dziesiętne, liczby zespolone i ujemne wymagają innych definicji oraz innych narzędzi. Pierwszość dotyczy liczb całkowitych większych od 1.
• Wynik dotyczy tylko jednej wartości. Sprawdzenie liczby 359 lub 367 nie mówi, ile liczb pierwszych jest w całym przedziale. Nie jest to dowód ani badanie gęstości liczb pierwszych.

Najczęstsze pytania