Sprawdzanie liczb pierwszych

Liczby pierwsze to fundamentalne elementy budulcowe wszystkich liczb całkowitych, stanowiące podstawę nowoczesnej kryptografii, w tym szyfrowania RSA, które zabezpiecza bankowość internetową i komunikację. To narzędzie pozwala sprawdzić pierwszość, rozłożyć dowolną liczbę na czynniki pierwsze i wygenerować listy liczb pierwszych w wybranym zakresie przy użyciu sita Eratostenesa. Praktyczne zastosowania obejmują m.in. upraszczanie ułamków (podobnie jak robi to nasz kalkulator ułamków), obliczanie NWW/NWD, zrozumienie bezpieczeństwa cyfrowego oraz rozwiązywanie problemów teorii liczb w programowaniu konkursowym.

star 4.8

Sprawdzanie liczb pierwszych calculator

tag Prime Number Checker
First 25 Primes
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
Key Facts
• 2 is the only even prime
• 1 is neither prime nor composite
• Check divisibility up to √n
check_circle Result
✓
97 is PRIME
The 25th prime number
Previous Prime
89
Next Prime
101
Divisibility Test
√97 ≈ 9.85, check up to 9
97 ÷ 2 = 48.5 (not divisible)
97 ÷ 3 = 32.33 (not divisible)
97 ÷ 5 = 19.4 (not divisible)
97 ÷ 7 = 13.86 (not divisible)
→ No divisors found, 97 is prime

lightbulb Tips

  • •2 is the only even prime number
  • •1 is neither prime nor composite
  • •Check divisors only up to √n
  • •All primes > 3 are of form 6k±1

table_chart First 100 Primes

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541
Prime Facts
Primes ≤ 100: 25
Primes ≤ 1000: 168
Twin primes: (3,5), (5,7), (11,13), (17,19)...

How to Use the Sprawdzanie liczb pierwszych

calculate

Wybierz typ sprawdzenia

Sprawdź pierwszość, rozłóż na czynniki, znajdź następną/poprzednią liczbę pierwszą lub wyświetl listę liczb pierwszych.

edit

Wpisz liczbę

Wprowadź liczbę do sprawdzenia lub użyj jej jako punktu wyjścia.

tune

Ustaw zakres (jeśli potrzebny)

Dla list liczb pierwszych wprowadź koniec zakresu.

visibility

Wyświetl wyniki

Sprawdź, czy liczba jest pierwsza, znajdź jej czynniki lub wygeneruj listę liczb pierwszych krok po kroku.

The Formula

Liczba pierwsza ma dokładnie dwa różne dodatnie dzielniki: 1 oraz samą siebie. Sprawdzenie podzielności do √n jest wystarczające, ponieważ dzielniki występują w parach.

n is prime if its only divisors are 1 and n

lightbulb Variables Explained

  • Prime Liczba mająca dokładnie 2 dzielniki: 1 oraz samą siebie
  • Composite Liczba mająca więcej niż 2 dzielniki
  • √n Wystarczy sprawdzić dzielniki do pierwiastka kwadratowego

tips_and_updates Pro Tips

1

2 to jedyna parzysta liczba pierwsza – wszystkie inne liczby parzyste są podzielne przez 2

2

Z definicji 1 nie jest ani liczbą pierwszą, ani złożoną

3

Aby sprawdzić, czy n jest liczbą pierwszą, wystarczy przetestować podzielność do √n

4

Liczby pierwsze bliźniacze to pary różniące się o 2: (3,5), (5,7), (11,13), (17,19)...

5

Wszystkie liczby pierwsze > 3 mają postać 6k±1 (ale nie każda liczba 6k±1 jest pierwsza)

6

Rozkład na czynniki pierwsze jest unikalny dla każdej liczby (Podstawowe twierdzenie arytmetyki)

Sprawdź, czy liczba jest pierwsza, znajdź jej czynniki pierwsze, wygeneruj listy liczb pierwszych i znajdź następne/poprzednie liczby pierwsze. Zobacz testy pierwszości krok po kroku.

Czym są liczby pierwsze?

Liczby pierwsze mają dokładnie dwa dzielniki: 1 oraz samą siebie.

Pierwsze liczby pierwsze to 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Liczby pierwsze są fundamentem wszystkich liczb całkowitych.

Rozkład na czynniki pierwsze

Każdą liczbę całkowitą > 1 można w unikalny sposób przedstawić jako iloczyn liczb pierwszych.

Na przykład 60 = 2² × 3 × 5.

Ma to fundamentalne znaczenie w matematyce i kryptografii.

Jak sprawdzić, czy liczba jest pierwsza?

Aby sprawdzić, czy liczba n jest pierwsza, należy przetestować, czy jakakolwiek liczba całkowita od 2 do pierwiastka kwadratowego z n dzieli ją bez reszty; jeśli żadna tego nie robi, n jest liczbą pierwszą.

Najpierw rozważ małe przypadki:

  • liczby mniejsze od 2 nie są pierwsze
  • 2 i 3 są liczbami pierwszymi
  • każda liczba parzysta większa od 2 jest złożona

Następnie przetestuj dzielniki nieparzyste aż do √n, ponieważ dzielniki zawsze występują w parach, których mniejszy element nie może przekroczyć pierwiastka kwadratowego.

Na przykład, sprawdzenie liczby 97 wymaga jedynie przetestowania 3, 5 i 7 (ponieważ √97 ≈ 9,85), a żadna z nich jej nie dzieli, więc 97 jest liczbą pierwszą. Wolfram MathWorld opisuje to jako dzielenie próbne, najbardziej bezpośredni test pierwszości.

Czym jest metoda pierwiastka kwadratowego w testowaniu pierwszości?

Metoda pierwiastka kwadratowego oznacza, że wystarczy przetestować potencjalne dzielniki tylko do √n, a nie aż do n.

Powodem jest to, że jeśli n = a × b, to przynajmniej jeden z czynników a lub b musi być mniejszy lub równy √n; w przeciwnym razie ich iloczyn przekroczyłby n. Jeśli więc poniżej √n nie znaleziono żadnego czynnika, to nie istnieje również żaden większy.

To znacznie zmniejsza nakład pracy: sprawdzenie, czy 9973 jest liczbą pierwszą, wymaga testowania dzielników tylko do około 99, a nie do prawie 10 000.

Khan Academy wykorzystuje ten argument parowania, aby wyjaśnić, dlaczego dzielenie próbne kończy się na pierwiastku kwadratowym, co czyni ręczne sprawdzanie pierwszości praktycznym.

Jak sito Eratostenesa generuje liczby pierwsze?

Sito Eratostenesa znajduje wszystkie liczby pierwsze do limitu N poprzez wielokrotne oznaczanie wielokrotności każdej liczby pierwszej jako złożone.

Zacznij od listy liczb całkowitych od 2 do N. Weź 2, oznacz 4, 6, 8, ... jako złożone; przejdź do następnej nieoznaczonej liczby, 3, i oznacz 6, 9, 12, ...; kontynuuj z 5, 7 i tak dalej. Liczby, które pozostaną nieoznaczone, są pierwsze.

Zastosowane do 30, sito pozostawia 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Nazwany na cześć greckiego matematyka Eratostenesa z Cyreny, algorytm ten (udokumentowany przez Encyclopaedia Britannica) jest jednym z najstarszych i najskuteczniejszych sposobów wypisywania liczb pierwszych w danym zakresie.

Czym jest podstawowe twierdzenie arytmetyki?

Podstawowe twierdzenie arytmetyki mówi, że każda liczba całkowita większa od 1 jest albo liczbą pierwszą, albo można ją zapisać jako iloczyn liczb pierwszych w dokładnie jeden sposób, z wyłączeniem kolejności czynników.

Na przykład 360 = 2³ × 3² × 5 i żadna inna kombinacja liczb pierwszych nie daje w iloczynie 360. Ta unikalność sprawia, że liczby pierwsze nazywane są budulcem liczb całkowitych.

Według Wolfram MathWorld, twierdzenie to stanowi podstawę faktoryzacji liczb pierwszych, obliczania największego wspólnego dzielnika i arytmetyki modularnej.

Nasz kalkulator wykorzystuje je podczas rozkładu liczby na czynniki, gwarantując, że otrzymany rozkład na czynniki pierwsze jest jedynym możliwym.

Czym są liczby pierwsze bliźniacze i luki między liczbami pierwszymi?

Liczby pierwsze bliźniacze to pary liczb pierwszych, które różnią się dokładnie o 2, takie jak (3, 5), (5, 7), (11, 13), (17, 19) i (29, 31).

Luka między kolejnymi liczbami pierwszymi na ogół rośnie wraz ze wzrostem liczb, chociaż liczby pierwsze bliźniacze wciąż się pojawiają. To, czy istnieje nieskończenie wiele liczb pierwszych bliźniaczych, jest słynną hipotezą liczb pierwszych bliźniaczych, która wciąż nie została udowodniona.

On-Line Encyclopedia of Integer Sequences (OEIS) kataloguje mniejsze elementy par liczb pierwszych bliźniaczych w ciągu A001359.

Zrozumienie luk między liczbami pierwszymi pomaga wyjaśnić, dlaczego liczby pierwsze stają się rzadsze: w pobliżu miliona liczby pierwsze są oddalone od siebie średnio o około 14, co jest trendem opisanym przez twierdzenie o liczbach pierwszych w NIST Digital Library of Mathematical Functions.

Jakie są praktyczne zastosowania liczb pierwszych?

Liczby pierwsze napędzają nowoczesną kryptografię, zwłaszcza szyfrowanie RSA, które zabezpiecza bankowość internetową, strony HTTPS i podpisy cyfrowe. RSA opiera się na fakcie, że pomnożenie dwóch dużych liczb pierwszych jest łatwe, ale rozłożenie iloczynu z powrotem na te liczby pierwsze jest obliczeniowo trudne.

Poza bezpieczeństwem, liczby pierwsze pojawiają się w:

  • ustalaniu rozmiaru tablic mieszających (tablice o długości będącej liczbą pierwszą zmniejszają liczbę kolizji)
  • generowaniu liczb pseudolosowych
  • kodach korekcyjnych
  • cyklach życiowych cykad, które wyewoluowały wokół lat będących liczbami pierwszymi, aby unikać drapieżników

Britannica zauważa, że faktoryzacja liczb pierwszych upraszcza również ułamki i obliczanie najmniejszej wspólnej wielokrotności. Ten kalkulator wspiera te zadania, rozkładając liczby na czynniki i generując liczby pierwsze zarówno do projektowania algorytmów, jak i do zadań domowych z matematyki.

Jaka jest różnica między liczbą pierwszą, złożoną a liczbą 1?

Liczba pierwsza ma dokładnie dwa różne dzielniki dodatnie, 1 i samą siebie, podczas gdy liczba złożona ma więcej niż dwa dzielniki.

Na przykład 13 jest liczbą pierwszą (dzielniki 1 i 13), a 12 jest liczbą złożoną (dzielniki 1, 2, 3, 4, 6, 12). Liczba 1 nie jest ani pierwsza, ani złożona, ponieważ ma tylko jeden dzielnik.

Ta konwencja utrzymuje przejrzystość podstawowego twierdzenia arytmetyki: gdyby 1 liczono jako liczbę pierwszą, faktoryzacje nie byłyby już unikalne, ponieważ można by wstawić dowolną liczbę jedynek.

Zarówno Encyclopaedia Britannica, jak i Khan Academy podkreślają to rozróżnienie, dlatego nasze narzędzie oznacza 1 oddzielnie od liczb pierwszych i złożonych.

Czym są liczby pierwsze Mersenne'a i jak duże mogą być liczby pierwsze?

Liczby pierwsze Mersenne'a to liczby pierwsze postaci 2^p − 1, gdzie wykładnik p sam jest liczbą pierwszą; przykłady to 3 (2² − 1), 7 (2³ − 1), 31 (2⁵ − 1) i 127 (2⁷ − 1).

Jednak nie każdy wykładnik będący liczbą pierwszą daje liczbę pierwszą: 2¹¹ − 1 = 2047 = 23 × 89 jest liczbą złożoną.

Liczby pierwsze Mersenne'a są ważne, ponieważ szybki test zwany testem Lucasa-Lehmera sprawia, że łatwiej je zweryfikować niż dowolne inne liczby, więc największe znane liczby pierwsze to prawie zawsze liczby pierwsze Mersenne'a mające dziesiątki milionów cyfr.

Great Internet Mersenne Prime Search (GIMPS) koordynuje wolontariuszy w celu ich odkrywania. Ciąg OEIS A000668 zawiera listę znanych liczb pierwszych Mersenne'a.

Typowe błędy podczas pracy z liczbami pierwszymi

  • Najczęstszym błędem jest traktowanie 1 jako liczby pierwszej; nie jest nią, ponieważ liczba pierwsza musi mieć dokładnie dwa dzielniki.
  • Innym błędem jest zapominanie, że 2 jest jedyną parzystą liczbą pierwszą, więc ludzie błędnie ją pomijają lub błędnie zakładają, że inne liczby parzyste mogą być pierwsze.
  • Trzecim błędem jest zbyt wczesne lub zbyt późne zakończenie dzielenia próbnego: należy przetestować wszystkie dzielniki do √n, a nie tylko kilka małych.
  • Ludzie mylą również faktoryzację liczb pierwszych z wypisaniem wszystkich dzielników; 12 ma dzielniki 1, 2, 3, 4, 6, 12, ale rozkład na czynniki pierwsze to tylko 2² × 3.
  • Wreszcie, założenie, że każda liczba postaci 6k ± 1 jest pierwsza, jest błędne; 25 = 6(4) + 1 jest liczbą złożoną.

Frequently Asked Questions

sell

Tags