Algorytm Euklidesa i Sito Eratostenesa — klasyka, która działa do dziś

Po co się tego uczymy?

Ponad 2000 lat temu, bez komputerów, Euklides i Eratostenes wymyślili metody, które dziś są fundamentem programowania — to dowód, że proste pomysły mogą być skuteczniejsze niż złożone wzory. Oba algorytmy pojawiają się na maturze rozszerzonej i pokazują pierwsze przykłady algorytmicznego myślenia: dzielenie problemu na kroki, powtarzalne operacje, warunek zakończenia.

Teoria

Algorytm Euklidesa służy do znajdowania największego wspólnego dzielnika (NWD) dwóch liczb — czyli największej liczby, która dzieli obie bez reszty. Przykład: NWD(20, 12) = 4.

Odkrycie Euklidesa — jeśli od większej liczby odejmiemy mniejszą, największy wspólny dzielnik SIĘ NIE ZMIENIA: NWD(a, b) = NWD(a - b, b). Dopóki jedna z liczb nie stanie się zerem, powtarzamy odejmowanie — druga liczba to wtedy NWD.

Współczesna, krótsza wersja zamiast wielokrotnego odejmowania używa RESZTY z dzielenia: NWD(a, b) = NWD(b, a mod b). Dzielimy a przez b, bierzemy resztę, i powtarzamy, aż reszta wyniesie 0.

Zastosowania NWD: uproszczenie ułamków (np. 12/18 → 2/3), kryptografia (szyfrowanie RSA), obliczenia w fizyce i chemii (proporcje), obliczanie NWW (najmniejszej wspólnej wielokrotności): NWW(a, b) = a * b / NWD(a, b).

Sito Eratostenesa znajduje WSZYSTKIE liczby pierwsze do zadanej granicy. Liczba pierwsza dzieli się TYLKO przez 1 i samą siebie (np. 2, 3, 5, 7, 11, 13...). Zamiast sprawdzać podzielność KAŻDEJ liczby osobno, Eratostenes wpadł na genialnie prosty pomysł: usuwać liczby, które MAJĄ dzielniki.

Zasada działania sita: (1) zapisz wszystkie liczby od 2 do n, (2) wybierz pierwszą liczbę, która nie jest skreślona — to liczba pierwsza, (3) skreśl WSZYSTKIE jej wielokrotności, (4) powtarzaj, aż dojdziesz do końca listy — pozostałe liczby to liczby pierwsze. Nazwa "sito" bierze się stąd, że algorytm "odsiewa" liczby złożone, zostawiając tylko pierwsze — jak sitko oddzielające makaron od wody.

Wspólna idea obu algorytmów, mimo że dzieli je 2000 lat: oba DZIELĄ problem na mniejsze kroki, oba wykonują POWTARZALNE operacje, oba mają KONIEC, gdy spełniony jest warunek (reszta 0 albo koniec listy). To dokładnie to, czego dziś uczymy w programowaniu: pętli, warunków, rekurencji i efektywności.

Schemat

ALGORYTM EUKLIDESA
48, 18
→ 48 % 18 = 12       → NWD(18, 12)
→ 18 % 12 = 6        → NWD(12, 6)
→ 12 % 6  = 0        → KONIEC (NWD = 6)

SITO ERATOSTENESA (do 30)
[2,3,4,5,6,7,8,9,10,11,12,...,30]
skreślamy wielokrotności 2, 3, 5...
→ zostają liczby pierwsze:
  [2,3,5,7,11,13,17,19,23,29]

Przykład z życia

Uproszczanie ułamków w kalkulatorze (12/18 zamienia się automatycznie na 2/3) korzysta właśnie z NWD, a szyfrowanie RSA — jeden z najpopularniejszych sposobów zabezpieczania danych w internecie — opiera się na własnościach liczb pierwszych, znajdowanych właśnie metodami podobnymi do sita Eratostenesa.

algorytm_euklidesa.py

# Algorytm Euklidesa - wersja iteracyjna (przez resztę z dzielenia)
def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print("NWD(48, 18) =", nwd(48, 18))
# Wynik: NWD(48, 18) = 6


# Algorytm Euklidesa - wersja rekurencyjna
def nwd_rek(a, b):
    if b == 0:
        return a
    else:
        return nwd_rek(b, a % b)

print("NWD(48, 18) =", nwd_rek(48, 18))
# Wynik: NWD(48, 18) = 6

sito_eratostenesa.py

# Sito Eratostenesa - znajdowanie wszystkich liczb pierwszych do n
def sito_eratostenesa(n):
    liczby = [True] * (n + 1)
    liczby[0] = liczby[1] = False

    for i in range(2, int(n**0.5) + 1):
        if liczby[i]:
            for j in range(i*i, n + 1, i):
                liczby[j] = False

    for i in range(2, n + 1):
        if liczby[i]:
            print(i, end=" ")

sito_eratostenesa(50)
# Wynik: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Komentarz i wyjaśnienie kodu

W nwd() linijka a, b = b, a % b to JEDNOCZESNE przypisanie — Python najpierw oblicza WSZYSTKIE wartości po prawej stronie, dopiero potem przypisuje je do zmiennych po lewej. Dzięki temu nie trzeba używać zmiennej tymczasowej do zamiany wartości miejscami.

W sito_eratostenesa() pętla zewnętrzna sprawdza liczby TYLKO do sqrt(n) (pierwiastka z n) — to kluczowa optymalizacja: jeśli liczba i większa niż sqrt(n) miałaby dzielnik złożony, ten dzielnik zostałby już wcześniej wykryty przy mniejszej liczbie. Pętla wewnętrzna zaczyna skreślanie od i*i (nie od 2*i), bo mniejsze wielokrotności i zostały już skreślone przez wcześniejsze, mniejsze liczby pierwsze.

Ćwiczenie samodzielne

Uruchom obie wersje (iteracyjną i rekurencyjną) algorytmu Euklidesa dla kilku par liczb i sprawdź, że dają ten sam wynik. Następnie uruchom sito Eratostenesa dla n=100 i policz, ile jest liczb pierwszych w tym zakresie.

Zadania do pracy własnej

Napisz program, który wczytuje dwie liczby od użytkownika i oblicza ich NWD metodą Euklidesa (możesz skopiować funkcję nwd() z przykładu).
Rozszerz program o obliczanie NWW (najmniejszej wspólnej wielokrotności) według wzoru NWW(a, b) = a * b / NWD(a, b). Zmodyfikuj sito Eratostenesa tak, żeby zapisywało znalezione liczby pierwsze do pliku pierwsze.txt zamiast wypisywać je na ekranie.
Napisz program, który najpierw wypisuje wszystkie liczby pierwsze z podanego przedziału (używając sita Eratostenesa), a potem dla KAŻDEJ PARY sąsiednich liczb pierwszych oblicza ich NWD (powinien zawsze wynosić 1, bo liczby pierwsze są względnie pierwsze — sprawdź, czy Twój program to potwierdza).

Typowe błędy

Próba obliczenia NWD przez sprawdzanie WSZYSTKICH możliwych dzielników zamiast użycia algorytmu Euklidesa — działa poprawnie, ale jest dużo wolniejsze dla dużych liczb; algorytm Euklidesa znajduje NWD w zaledwie kilku krokach, niezależnie od wielkości liczb.

Rozpoczynanie skreślania wielokrotności w sicie od 2*i zamiast i*i — działa poprawnie, ale jest mniej wydajne, bo powtórnie skreśla liczby już skreślone przez wcześniejsze, mniejsze czynniki pierwsze.

Zapominanie o ustawieniu liczby[0] i liczby[1] na False w sicie Eratostenesa — 0 i 1 z definicji NIE są liczbami pierwszymi, a pominięcie tego kroku wypaczy wynik.

Nawiązanie do egzaminu zawodowego

Oba algorytmy pojawiają się w zadaniach maturalnych z zakresu rozszerzonego jako klasyczne przykłady algorytmów iteracyjnych i tablicowych — sito Eratostenesa dodatkowo trenuje myślenie o OPTYMALIZACJI (dlaczego sprawdzamy tylko do pierwiastka z n), co prowadzi wprost do tematu złożoności obliczeniowej (ostatnia lekcja tego działu).