Kalkulator liczb pierwszych

Kalkulator liczb pierwszych - Suma, liczba i wyszukiwanie liczb pierwszych

🔢 Oblicz sumę liczb pierwszych, znajdź liczby pierwsze w zakresie, sprawdź czy liczba jest pierwsza oraz wyznacz N-tą liczbę pierwszą. Szybki algorytm Sita Eratostenesa z wizualizacją.

Czym są liczby pierwsze?

Liczba pierwsza to liczba naturalna większa niż 1, której nie da się utworzyć przez pomnożenie dwóch mniejszych liczb naturalnych. Innymi słowy, ma dokładnie dwa dzielniki: 1 i samą siebie.

Pierwsze 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

Jak sprawdzić, czy liczba jest pierwsza?

Metoda 1 - Dzielenie próbne:

• Sprawdź, czy n jest podzielne przez jakąkolwiek liczbę od 2 do √n
• Jeśli tak, to liczba złożona (nie jest pierwsza)
• Jeśli nie, to liczba pierwsza

Przykład: Czy 17 jest liczbą pierwszą?

• √17 ≈ 4.12, więc sprawdzamy podzielność przez 2, 3, 4
• 17 ÷ 2 = 8.5 (nie dzieli się)
• 17 ÷ 3 = 5.67 (nie dzieli się)
• 17 ÷ 4 = 4.25 (nie dzieli się)
• Wynik: 17 jest liczbą pierwszą!

Sito Eratostenesa

Starożytny algorytm do znalezienia wszystkich liczb pierwszych do n:

• Krok 1: Wypisz wszystkie liczby od 2 do n
• Krok 2: Zaznacz 2 jako pierwszą i wykreśl wszystkie wielokrotności 2
• Krok 3: Znajdź następną niewykreśloną liczbę (3) i zaznacz jako pierwszą
• Krok 4: Wykreśl wszystkie wielokrotności tej liczby pierwszej
• Krok 5: Powtarzaj do √n
• Wynik: Wszystkie niewykreślone liczby są pierwsze

Suma liczb pierwszych

Suma pierwszych n liczb pierwszych:

• Pierwsze 10: 2+3+5+7+11+13+17+19+23+29 = 129
• Pierwsze 100: suma = 24 133
• Pierwsze 1000: suma = 3 682 913

Suma liczb pierwszych do n:

• Do 10: 2+3+5+7 = 17
• Do 100: suma = 1 060
• Do 1000: suma = 76 127

Twierdzenie o liczbach pierwszych

Liczba liczb pierwszych mniejszych niż n jest w przybliżeniu równa n/ln(n):

• Do 100: ~25 liczb pierwszych (dokładnie: 25)
• Do 1 000: ~145 (dokładnie: 168)
• Do 10 000: ~1 086 (dokładnie: 1 229)
• Do 100 000: ~8 686 (dokładnie: 9 592)

Rodzaje liczb pierwszych

Liczby bliźniacze: liczby pierwsze, które różnią się o 2

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

Liczby Mersenne’a: postać 2ᵖ - 1, gdzie p jest liczbą pierwszą

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• Największa znana liczba pierwsza jest typu Mersenne’a (24,8 mln cyfr!)

Liczby Sophie Germain: liczba pierwsza p, dla której 2p+1 też jest pierwsza

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

Liczby Fermata: postać 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65,537
• Znanych jest tylko 5 liczb Fermata będących pierwszymi

Zastosowania liczb pierwszych

Kryptografia (RSA):

• Opiera się na trudności rozkładu dużych liczb na czynniki
• Wykorzystuje dwie duże liczby pierwsze (setki cyfr)
• Zabezpiecza bankowość online, e-maile i strony internetowe

Tablice mieszające:

• Rozmiary będące liczbami pierwszymi zmniejszają liczbę kolizji
• Stosowane w bazach danych i cache

Generowanie liczb losowych:

• Liczby pierwsze tworzą lepsze sekwencje pseudolosowe
• Używane w symulacjach i grach

Ciekawostki o liczbach pierwszych

• Nieskończoność: udowodniona przez Euklidesa ~300 p.n.e. – liczby pierwsze się nie kończą
• Luki: mogą być dowolnie duże (brak liczb pierwszych przez bardzo długi ciąg)
• Hipoteza Goldbacha: każda liczba parzysta > 2 jest sumą dwóch liczb pierwszych (nieudowodnione!)
• Hipoteza Riemanna: milionowa nagroda za dowód dotyczący rozkładu liczb pierwszych
• Odstępy między liczbami pierwszymi: różnica kolejnych liczb pierwszych rośnie
• Prawdopodobieństwo: losowa liczba n ma ~1/ln(n) szansy bycia pierwszą

Rekordy

• Największa znana liczba pierwsza: 2^82,589,933 - 1 (odkryta w 2018, 24 862 048 cyfr)
• Największe liczby bliźniacze: 2,996,863,034,895 × 2^1,290,000 ± 1
• Obliczenia: GIMPS (Great Internet Mersenne Prime Search) – projekt rozproszony

Najczęstsze nieporozumienia

• 1 NIE jest pierwsza: według współczesnej definicji (musi mieć dokładnie 2 dzielniki)
• Nie wszystkie liczby nieparzyste są pierwsze: 9, 15, 21, 25... są złożone
• Wzór na wszystkie liczby pierwsze: nie istnieje prosty wzór generujący wszystkie liczby pierwsze
• Wzór w liczbach pierwszych: brak przewidywalnego schematu (wyglądają „losowo”)

💡 Wskazówka: sprawdzając, czy duża liczba jest pierwsza, wystarczy testować dzielniki do jej pierwiastka! Na przykład, aby sprawdzić 997, trzeba testować tylko do √997 ≈ 31.6, czyli 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Jeśli żadna z tych liczb nie dzieli 997 bez reszty, to 997 jest pierwsza. Dodatkowo, poza 2 i 3, wszystkie liczby pierwsze mają postać 6k±1, co może jeszcze przyspieszyć wyszukiwanie.