Sito Eratostenesa

Wprowadzenie

Sito Eratostenesa to starożytny, ale niezwykle efektywny algorytm służący do znajdowania wszystkich liczb pierwszych do zadanej liczby N. Został opracowany przez greckiego matematyka Eratostenesa z Cyreny (276-194 p.n.e.).

Algorytm działa na zasadzie stopniowego "odsiewania" liczb złożonych, pozostawiając tylko liczby pierwsze.

Sito Eratostenesa jest wykorzystywane w:

  • Kryptografii (generowanie dużych liczb pierwszych)
  • Teorii liczb (badanie rozkładu liczb pierwszych)
  • Optymalizacji algorytmów (preprocessing dla testów pierwszości)
  • Problemach kombinatorycznych
  • Faktoryzacji liczb
  • Generowaniu kluczy RSA

Idea algorytmu

Zasada działania

1. Utwórz listę liczb od 2 do N (wszystkie początkowo "kandydaci")
2. Dla każdej liczby p (zaczynając od 2):
   a) Jeśli p jest oznaczona jako pierwsza:
      - Oznacz wszystkie wielokrotności p (2p, 3p, 4p, ...) jako złożone
   b) Przejdź do następnej nieoznaczonej liczby
3. Wszystkie nieoznaczone liczby to liczby pierwsze

Wizualizacja procesu

Krok 0: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
        Wszystkie liczby są kandydatami

Krok 1 (p=2): Skreśl wielokrotności 2
        [2, 3, X, 5, X, 7, X, 9, X, 11, X, 13, X, 15]

Krok 2 (p=3): Skreśl wielokrotności 3
        [2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X]

Krok 3 (p=5): Skreśl wielokrotności 5
        [2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X]
        (nic nowego - wszystkie już skreślone)

Wynik: [2, 3, 5, 7, 11, 13] - liczby pierwsze do 15

Implementacja podstawowa

Wersja klasyczna

Wyjście:

=== Sito Eratostenesa (podstawowa wersja) ===

Liczby pierwsze do  10:   4 liczb
   [2, 3, 5, 7]

Liczby pierwsze do  30:  10 liczb
   [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Liczby pierwsze do  50:  15 liczb

Liczby pierwsze do 100:  25 liczb

Optymalizacje algorytmu

1. Optymalizacja: zaczynaj od p²

Obserwacja: Gdy przetwarzamy liczbę p, wszystkie wielokrotności < p² już zostały oznaczone przez mniejsze liczby pierwsze.

Przykład: Dla p=7: - 7×2 = 14 (już skreślone przez 2) - 7×3 = 21 (już skreślone przez 3) - 7×5 = 35 (już skreślone przez 5) - 7×7 = 49 (pierwszy nowy do skreślenia!)

Wyjście:

=== Sito z optymalizacją (p²) ===

Zakres: do 1,000,000
Znaleziono: 78,498 liczb pierwszych
Czas: 0.0523 s

2. Optymalizacja: pomijaj parzyste

Obserwacja: Poza 2, wszystkie liczby pierwsze są nieparzyste.

Wyjście:

=== Sito z optymalizacją (bez parzystych) ===

Zakres: do 1,000,000
Znaleziono: 78,498 liczb pierwszych
Czas: 0.0387 s

Pierwsze 20: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
Ostatnie 10: [999907, 999917, 999931, 999953, 999959, 999961, 999979, 999983, 999985, 999991]

3. Sito segmentowane (dla dużych N)

Problem: Dla bardzo dużego N, klasyczne sito wymaga O(N) pamięci.

Rozwiązanie: Dziel zakres na segmenty i przetwarzaj każdy osobno.

Wyjście:

=== Sito segmentowane ===

Zakres: do 1,000,000
Znaleziono: 78,498 liczb pierwszych
Czas: 0.0891 s

Praktyczne zastosowania

1. Znajdowanie N-tej liczby pierwszej

Wyjście:

=== N-ta liczba pierwsza ===

N          N-ta liczba pierwsza
-----------------------------------
1          2
10         29
100        541
1000       7919
10000      104729

2. Liczby pierwsze w zakresie [L, R]

Wyjście:

=== Liczby pierwsze w zakresie ===

[1, 20]: 8 liczb pierwszych
   [2, 3, 5, 7, 11, 13, 17, 19]

[50, 100]: 10 liczb pierwszych
   Pierwsze 5: [53, 59, 61, 67, 71]

[1000, 1050]: 11 liczb pierwszych
   Pierwsze 5: [1009, 1013, 1019, 1021, 1031]

3. Liczby pierwsze bliźniacze

Wyjście:

=== Liczby pierwsze bliźniacze ===

Liczby bliźniacze do 200:

 1. (3, 5)
 2. (5, 7)
 3. (11, 13)
 4. (17, 19)
 5. (29, 31)
 6. (41, 43)
 7. (59, 61)
 8. (71, 73)
 9. (101, 103)
10. (107, 109)

... (łącznie 15 par)

4. Funkcja Eulera φ(n) przez sito

Funkcja Eulera φ(n): liczba liczb ≤ n względnie pierwszych z n.

Wyjście:

=== Funkcja Eulera przez sito ===

n     φ(n)     Interpretacja
--------------------------------------------------
1     1        1 liczb < 1 względnie pierwszych z 1
2     1        1 liczb < 2 względnie pierwszych z 2
3     2        2 liczb < 3 względnie pierwszych z 3
4     2        2 liczb < 4 względnie pierwszych z 4
5     4        4 liczb < 5 względnie pierwszych z 5
6     2        2 liczb < 6 względnie pierwszych z 6
7     6        6 liczb < 7 względnie pierwszych z 7
8     4        4 liczb < 8 względnie pierwszych z 8
9     6        6 liczb < 9 względnie pierwszych z 9
...

Porównanie wydajności

Wyjście (przykładowe):

=== Benchmark różnych wersji sita ===

N            Algorytm                       Czas (ms)    Liczb pierwszych
---------------------------------------------------------------------------
10000        Podstawowe                         1.23           1229
10000        Optymalizacja v1 (p²)              0.98           1229
10000        Optymalizacja v2 (bez parzystych)  0.67           1229
10000        Segmentowane                       1.45           1229
100000       Podstawowe                        12.34           9592
100000       Optymalizacja v1 (p²)             10.12           9592
100000       Optymalizacja v2 (bez parzystych)  7.23           9592
100000       Segmentowane                       9.87           9592
1000000      Podstawowe                       134.56          78498
1000000      Optymalizacja v1 (p²)            112.34          78498
1000000      Optymalizacja v2 (bez parzystych) 78.91          78498
1000000      Segmentowane                     101.23          78498

Złożoność obliczeniowa

Analiza teoretyczna

Algorytm Złożoność czasowa Złożoność pamięciowa
Podstawowe sito O(n log log n) O(n)
Optymalizacja (p²) O(n log log n) O(n)
Optymalizacja (bez parzystych) O(n log log n) O(n/2)
Sito segmentowane O(n log log n) O(√n + segment)

Porównanie z innymi metodami

Metoda Zastosowanie Złożoność
Sito Eratostenesa Wiele liczb pierwszych do N O(n log log n)
Test √n Pojedyncza liczba O(√n)
Miller-Rabin Pojedyncza liczba (duża) O(k log³ n)

Kiedy używać sita? - Gdy potrzebujesz wielu liczb pierwszych do N - Gdy będziesz wielokrotnie sprawdzać pierwszość w zakresie - Gdy N ≤ 10⁷ (dla większych: sito segmentowane)

Podsumowanie

Kluczowe cechy sita Eratostenesa

✅ Wydajność: O(n log log n) - bardzo szybkie ✅ Prostota: Łatwa implementacja i zrozumienie ✅ Kompletność: Znajduje wszystkie liczby pierwsze do N ✅ Deterministyczność: Zawsze poprawny wynik ✅ Optymalizacje: Wiele możliwości usprawnienia

Optymalizacje

✅ Zaczynaj od p²: Pomijaj już oznaczone wielokrotności ✅ Pomijaj parzyste: Oszczędność 50% pamięci ✅ Sito segmentowane: Dla bardzo dużych N ✅ Koło (wheel): Pomijaj wielokrotności 2, 3, 5

Zastosowania

✅ Generowanie liczb pierwszych: Do zadanego limitu ✅ Faktoryzacja: Lista dzielników pierwszych ✅ Kryptografia: Preprocessing dla RSA ✅ Funkcja Eulera: Obliczanie φ(n) ✅ Problemy kombinatoryczne: Liczby względnie pierwsze

Co dalej?

Po opanowaniu sita Eratostenesa, następne kroki to:

  1. Lekcja 67: Algorytm Euklidesa - NWD
  2. Największy wspólny dzielnik
  3. Wersja rekurencyjna i iteracyjna

  4. Rozszerzony algorytm Euklidesa

  5. Lekcja 68: NWD i NWW - zastosowania

  6. Najmniejsza wspólna wielokrotność
  7. Zastosowania praktyczne

  8. Liczby względnie pierwsze

  9. Lekcja 69: Rozkład na czynniki pierwsze

  10. Faktoryzacja liczb
  11. Algorytmy rozkładu
  12. Zastosowania

Zadania praktyczne

Zadanie 1: Liczby pierwsze Sophie Germain

Znajdź liczby pierwsze p takie, że 2p+1 też jest pierwsze (do N=1000).

Zadanie 2: Największa luka

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

Zadanie 3: Gęstość liczb pierwszych

Oblicz i narysuj wykres gęstości liczb pierwszych (π(n)/n) dla n = 10, 100, 1000, ...

Zadanie 4: Sito z kołem (wheel)

Zaimplementuj sito z optymalizacją "koła" pomijającą wielokrotności 2, 3 i 5.

Zadanie 5: Suma liczb pierwszych

Oblicz sumę wszystkich liczb pierwszych do 2,000,000 (Project Euler #10).

Następna lekcja: Algorytm Euklidesa - największy wspólny dzielnik (NWD)

Wróć do spisu lekcji