Sprawdzanie liczb pierwszych
Sprawdz czy liczba jest pierwsza. Test Millera-Rabina dla duzych liczb. Generator liczb pierwszych. Bezpłatnie.
-
1Wprowadź dane
Wpisz treść, wklej tekst lub załaduj plik z dysku. -
2Kliknij przycisk
Narzędzie natychmiast przetworzy Twoje dane w przeglądarce. -
3Pobierz wynik
Skopiuj gotowy tekst lub zapisz plik na urządzeniu.
return "Wynik gotowy w 0.1s";
}
Oceń to narzędzie:
Powiązane narzędzia
Inne narzędzia, które mogą Ci się przydaćSprawdzanie liczb pierwszych — test pierwszości i faktoryzacja
Narzędzie do sprawdzania liczb pierwszych weryfikuje, czy podana liczba jest pierwsza, i pokazuje jej rozkład na czynniki pierwsze. Obsługuje duże liczby — przydatne dla studentów matematyki, uczniów i programistów zainteresowanych teorią liczb i kryptografią.
Czym jest liczba pierwsza?
Liczba pierwsza (prime number) to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie. Liczby pierwsze to: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Liczby złożone (nie pierwsze) to takie, które mają więcej niż dwa dzielniki — np. 4 = 2×2, 6 = 2×3, 12 = 2×2×3. Liczba 1 nie jest uznawana ani za pierwszą, ani za złożoną — jest jednostką.
Jak sprawdzić, czy liczba jest pierwsza?
Metoda brute force — sprawdź, czy żadna liczba od 2 do √n nie dzieli n bez reszty. Wystarczy sprawdzać do √n, bo jeśli n = a×b i a > √n, to b < √n i zostałoby znalezione wcześniej. Złożoność: O(√n). Sito Eratostenesa — efektywna metoda do znalezienia wszystkich liczb pierwszych do N. Iteracyjnie wykreśla wielokrotności każdej znalezionej liczby pierwszej. Test Millera-Rabina — probabilistyczny test pierwszości dla bardzo dużych liczb (kryptografia). Używany w bibliotekach kryptograficznych (OpenSSL, Java BigInteger).
Dlaczego liczby pierwsze są ważne w kryptografii?
Kryptografia asymetryczna (RSA, DSA, Diffie-Hellman) opiera się na trudności faktoryzacji dużych liczb złożonych. Jeśli N = p × q, gdzie p i q to duże liczby pierwsze (512–2048 bitów), znalezienie p i q znając tylko N jest computationally infeasible — najlepszy znany algorytm (GNFS) działa w czasie sub-wykładniczym, ale jest zbyt wolny dla kluczy 2048-bit+. Klucze RSA 2048-bit będą bezpieczne przez dziesiątki lat.
Rozkład na czynniki pierwsze
Każda liczba złożona ma dokładnie jeden rozkład na czynniki pierwsze (Fundamentalne Twierdzenie Arytmetyki): 12 = 2² × 3, 360 = 2³ × 3² × 5, 1001 = 7 × 11 × 13. Rozkład pokazuje "budulce" liczby. Narzędzie pokazuje rozkład i weryfikuje wynik: iloczyn czynników powinien dać oryginalną liczbę.
Najczęściej zadawane pytania
Ile jest liczb pierwszych do 100?
Do 100 jest 25 liczb pierwszych: 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. Gęstość liczb pierwszych maleje wraz ze wzrostem liczb — wśród liczb od 1 do 100 jest 25% pierwszych, od 1 do 1000 — 16,8%, od 1 do 1 000 000 — 7,85%.
Czy istnieje największa liczba pierwsza?
Nie — liczb pierwszych jest nieskończenie wiele (dowód Euklidesa z ok. 300 p.n.e.). Największa znana liczba pierwsza (stan na 2024) to liczba Mersenne'a 2^136279841 − 1, znaleziona przez projekt GIMPS. Ma ponad 41 milionów cyfr. Poszukiwanie coraz większych liczb pierwszych Mersenne'a to aktywny projekt naukowy.
Dlaczego 1 nie jest liczbą pierwszą?
Definicja liczby pierwszej wymaga dokładnie dwóch dzielników. Liczba 1 ma tylko jeden dzielnik (siebie samą), więc nie spełnia definicji. Historycznie matematycy spierali się o status 1 — przez wieki była uważana za pierwszą. Współcześnie wyklucza się ją z definicji, bo jej włączenie zepsułoby Fundamentalne Twierdzenie Arytmetyki (niejednoznaczność rozkładu: 6 = 2×3 = 1×2×3 = 1²×2×3...).
Jak szybko sprawdzić pierwszość liczby w Python?
def is_prime(n): return n > 1 and all(n % i for i in range(2, int(n**0.5)+1)). Dla dużych liczb użyj: from sympy import isprime; isprime(n) — sympy używa Millera-Rabina i testu Solovay-Strassen. Wbudowane: from cryptography.hazmat.primitives.asymmetric import rsa dla kryptograficznych zastosowań.
Co to są liczby bliźniacze (twin primes)?
Liczby bliźniacze to pary liczb pierwszych różniących się o 2: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43)... Hipoteza o nieskończoności liczb bliźniaczych (Twin Prime Conjecture) jest jednym z nierozwiązanych problemów matematyki. W 2013 Zhang Yitang udowodnił, że istnieje nieskończona liczba par pierwszych różniących się o mniej niż 70 milionów (wynik następnie ulepszany do 246).