Liczby pierwsze - test pierwszości

Wprowadzenie

Liczba pierwsza to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie. Liczby pierwsze są fundamentalnym pojęciem w matematyce i mają kluczowe zastosowania w informatyce.

Testy pierwszości są wykorzystywane w:

Kryptografii (RSA, generowanie kluczy)
Funkcjach haszujących (wybór rozmiarów tablic)
Generatorach liczb pseudolosowych
Algorytmach faktoryzacji
Teorii kodowania
Testowaniu oprogramowania

Przykłady liczb pierwszych: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...

Liczby złożone: liczby mające więcej niż 2 dzielniki (4, 6, 8, 9, 10...)

Podstawowa definicja

Matematyczna definicja

Liczba n > 1 jest pierwsza ⟺ nie istnieje liczba d taka, że:

2 ≤ d < n  oraz  n mod d = 0

Innymi słowy: n nie dzieli się przez żadną liczbę oprócz 1 i n.

Algorytmy sprawdzania pierwszości

1. Metoda naiwna (trial division)

Algorytm:

Sprawdź wszystkie potencjalne dzielniki od 2 do n-1:
  Jeśli n dzieli się przez jakiś dzielnik → liczba złożona
  Jeśli nie znaleziono dzielnika → liczba pierwsza

Implementacja:

Wyjście:

=== Test pierwszości (metoda naiwna) ===

   1 → złożona
   2 → PIERWSZA
   3 → PIERWSZA
   4 → złożona
   5 → PIERWSZA
  10 → złożona
  11 → PIERWSZA
  15 → złożona
  17 → PIERWSZA
  20 → złożona
  23 → PIERWSZA
  25 → złożona
  29 → PIERWSZA
  30 → złożona
  97 → PIERWSZA
 100 → złożona

Złożoność: O(n) - bardzo wolne dla dużych liczb!

2. Optymalizacja: sprawdzanie do √n

Obserwacja: Jeśli n jest złożona, to ma dzielnik ≤ √n

Dlaczego?

Jeśli n = a × b  i  a > √n  to  b < √n

Czyli wystarczy sprawdzić dzielniki do √n!

Implementacja:

Wyjście:

=== Test pierwszości (√n) ===

Liczba     √n (limit)      Wynik
----------------------------------------
2          2               PIERWSZA
97         10              PIERWSZA
100        11              złożona
101        11              PIERWSZA
1009       32              złożona
1013       32              PIERWSZA
10007      101             złożona
10009      101             PIERWSZA

Poprawa wydajności: z O(n) na O(√n) - masywna optymalizacja!

3. Dalsze optymalizacje

Wyjście:

=== Test pierwszości (zoptymalizowany) ===

Liczba: 1000000007
Wynik: PIERWSZA
Czas: 0.0124 ms

4. Test Miller-Rabin (probabilistyczny)

Algorytm probabilistyczny - bardzo szybki dla dużych liczb, ale może dać błędną odpowiedź z małym prawdopodobieństwem.

Wyjście:

=== Test Miller-Rabin (probabilistyczny) ===

     1000000007 → PIERWSZA  ✓
     1000000009 → PIERWSZA  ✓
     1000000010 → złożona   ✓
      982451653 → PIERWSZA  ✓
      982451654 → złożona   ✓

Miller-Rabin jest bardzo szybki i praktycznie zawsze poprawny (prawdopodobieństwo błędu < 10⁻³⁰ dla k=10).

Porównanie algorytmów

Wyjście (przykładowe):

=== Benchmark testów pierwszości ===

Liczba          Typ                  Algorytm             Czas (ms)
----------------------------------------------------------------------
97              mała pierwsza        √n optimized           0.0008
97              mała pierwsza        Miller-Rabin           0.0042
10007           średnia pierwsza     √n optimized           0.0089
10007           średnia pierwsza     Miller-Rabin           0.0055
1000000007      duża pierwsza        √n optimized           0.2145
1000000007      duża pierwsza        Miller-Rabin           0.0063
1000000000      duża złożona         √n optimized           0.0004
1000000000      duża złożona         Miller-Rabin           0.0051

Praktyczne zastosowania

1. Generowanie liczby pierwszej w zakresie

Wyjście:

=== Znajdowanie następnej liczby pierwszej ===

Początek:       1 → Następna pierwsza: 2
Początek:      10 → Następna pierwsza: 11
Początek:     100 → Następna pierwsza: 101
Początek:    1000 → Następna pierwsza: 1009
Początek:   10000 → Następna pierwsza: 10007
Początek:  100000 → Następna pierwsza: 100003

2. Policzenie liczb pierwszych do N

Wyjście:

=== Liczba pierwszych do N ===

N          Liczba pierwszych    Gęstość
---------------------------------------------
10         4                    40.00%
100        25                   25.00%
1000       168                  16.80%
10000      1229                 12.29%

3. Sprawdzanie liczb bliźniaczych

Liczby bliźniacze: pary liczb pierwszych różniących się o 2 (np. 3 i 5, 11 i 13, 17 i 19).

Wyjście:

=== Liczby pierwsze bliźniacze ===

Liczby bliźniacze do 100:

(3, 5)
(5, 7)
(11, 13)
(17, 19)
(29, 31)
(41, 43)
(59, 61)
(71, 73)

Znaleziono 8 par

Złożoność obliczeniowa

Porównanie algorytmów

Algorytm	Złożoność czasowa	Złożoność pamięciowa	Typ
Naiwny	O(n)	O(1)	Deterministyczny
√n optimized	O(√n)	O(1)	Deterministyczny
Miller-Rabin	O(k × log³ n)	O(1)	Probabilistyczny
AKS	O(log⁶ n)	O(log n)	Deterministyczny

gdzie: - n = liczba testowana - k = liczba iteracji Miller-Rabin

Podsumowanie

Kluczowe algorytmy

Algorytm	Kiedy używać	Zalety	Wady
√n optimized	Małe/średnie liczby (< 10⁹)	Prosty, deterministyczny	Wolny dla dużych n
Miller-Rabin	Duże liczby (> 10⁹)	Bardzo szybki	Probabilistyczny
Sito Eratostenesa	Wiele liczb do N	Szybkie dla zakresu	Wymaga pamięci O(n)

Kluczowe fakty

✅ Liczba pierwsza: ma tylko 2 dzielniki (1 i siebie) ✅ 2 jest jedyną parzystą liczbą pierwszą ✅ Każda liczba złożona ma dzielnik ≤ √n ✅ Gęstość liczb pierwszych maleje (twierdzenie o liczbach pierwszych) ✅ Miller-Rabin praktycznie zawsze poprawny dla k ≥ 10

Zastosowania

✅ Kryptografia: generowanie kluczy RSA ✅ Funkcje hash: rozmiary tablic ✅ Generatory liczb losowych ✅ Teoria kodowania ✅ Faktoryzacja

Co dalej?

Po opanowaniu testów pierwszości, następne kroki to:

Lekcja 66: Sito Eratostenesa
Efektywne generowanie wielu liczb pierwszych
Optymalizacje pamięciowe
Lekcja 67: Algorytm Euklidesa - NWD
Największy wspólny dzielnik
Liczby względnie pierwsze
Lekcja 69: Rozkład na czynniki pierwsze
Faktoryzacja liczb
Zastosowania

Zadania praktyczne

Zadanie 1: Generator liczb pierwszych

Napisz funkcję generującą N kolejnych liczb pierwszych.

Zadanie 2: Liczby Mersenne'a

Sprawdź które z liczb postaci 2ⁿ - 1 są pierwsze dla n ≤ 20.

Zadanie 3: Test Fermata

Zaimplementuj test pierwszości Fermata i porównaj z Miller-Rabin.

Zadanie 4: Rozwiń

Znajdź największą lukę między kolejnymi liczbami pierwszymi do 1,000,000.

Następna lekcja: Sito Eratostenesa - efektywne generowanie liczb pierwszych