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

1. Wstęp – matematyka, która przetrwała 2000 lat

W czasach, gdy nie było komputerów, ludzie też musieli liczyć – tylko robili to głową, kredą albo patykiem na piasku.
Nie mieli kalkulatorów, ale mieli genialne pomysły, które dziś nazywamy algorytmami.

Dwóch starożytnych matematyków – Euklides i Eratostenes – opracowało metody, które do dziś są podstawą programowania.
Ich algorytmy były tak przemyślane, że w XXI wieku nadal uczymy ich uczniów informatyki.
Zobaczmy, dlaczego.

Algorytm Euklidesa

O co chodzi?

Algorytm Euklidesa służy do znajdowania największego wspólnego dzielnika (NWD) dwóch liczb.
Czyli: jaka liczba „dzieli” obie bez reszty?

Przykład:
NWD(20, 12) = 4
bo 4 dzieli i 20, i 12.

3. Jak to odkrył Euklides

Ponad 2000 lat temu Euklides zauważył prostą zasadę:

Jeśli od większej liczby odejmiemy mniejszą –
to największy wspólny dzielnik się nie zmienia.

Czyli:

NWD(a, b) = NWD(a - b, b)

Dopóki jedna z liczb nie stanie się zerem, powtarzamy odejmowanie.
Wtedy druga liczba to właśnie NWD.

4. Wersja prostsza – z resztą z dzielenia

Współczesna wersja jest krótsza:

NWD(a, b) = NWD(b, a mod b)

Czyli dzielimy a przez b, bierzemy resztę z dzielenia,
i powtarzamy, aż reszta wyniesie 0.

5. Przykład krok po kroku

Znajdź NWD(48, 18):

48 mod 18 = 12      → NWD(18, 12)
18 mod 12 = 6       → NWD(12, 6)
12 mod 6 = 0        → KONIEC
Wynik: 6

Największy wspólny dzielnik to 6.

6. Algorytm Euklidesa w Pythonie

Wersja iteracyjna:

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print("NWD(48, 18) =", nwd(48, 18))

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print("NWD(48, 18) =", nwd(48, 18))

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))

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

NWD(48, 18) = 6

7. Gdzie to się przydaje

uproszczenie ułamków (np. 12/18 → 2/3),
kryptografia (szyfrowanie RSA),
obliczenia w fizyce i chemii (np. proporcje),
algorytmy z największym wspólnym dzielnikiem w tle (np. NWW).

Sito Eratostenesa

Kim był Eratostenes

Eratostenes z Cyreny żył w III wieku p.n.e.
Był matematykiem, astronomem i bibliotekarzem w Aleksandrii.
Jako pierwszy obliczył obwód Ziemi (i pomylił się tylko o 1%)!
Ale zasłynął z czegoś prostszego – sposobu znajdowania liczb pierwszych.

9. Co to jest liczba pierwsza

Liczba pierwsza to taka, która dzieli się tylko przez 1 i samą siebie.
Na przykład:
2, 3, 5, 7, 11, 13, 17…

10. Pomysł Eratostenesa

Eratostenes wymyślił genialnie prostą metodę:
zamiast próbować dzielić każdą liczbę po kolei, usuwał te, które mają dzielniki.

11. Zasada działania sita

Zapisz wszystkie liczby od 2 do n.
Wybierz pierwszą liczbę, która nie jest skreślona – to liczba pierwsza.
Skreśl wszystkie jej wielokrotności (czyli 2×p, 3×p, 4×p itd.).
Powtarzaj, aż dojdziesz do końca listy.

Pozostałe liczby to liczby pierwsze.

12. Sito Eratostenesa w Pythonie

To właśnie zadanie, które masz już na stronie:
👉 Sito Eratostenesa – zadanie

Poniżej wersja edukacyjna kodu z opisem:

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)

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

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

13. Dlaczego to jest „sito”

Bo „odsiewa” liczby złożone, zostawiając tylko pierwsze –
tak jak sitko w kuchni oddziela makaron od wody. 🍝

14. Wspólna idea z algorytmem Euklidesa

Choć Euklides i Eratostenes żyli ponad 2000 lat temu, ich pomysły są pierwszymi przykładami algorytmicznego myślenia:

oba dzielą problem na mniejsze kroki,
oba wykonują powtarzalne operacje,
oba mają koniec, gdy spełniony jest warunek (reszta 0 lub koniec listy).

To dokładnie to, czego dziś uczymy w programowaniu: pętli, warunków, rekurencji i efektywności.

15. Zadania dla ucznia

Zadanie 1 – NWD

Napisz program, który wczytuje dwie liczby i oblicza ich NWD metodą Euklidesa.
Dodaj wersję rekurencyjną i sprawdź, czy daje ten sam wynik.
Rozszerz program tak, by obliczał NWW (najmniejszą wspólną wielokrotność) według wzoru:
NWW(a, b) = a * b / NWD(a, b)

Zadanie 2 – Liczby pierwsze

Skopiuj kod sita Eratostenesa i zmień zakres na 100.
Zlicz, ile liczb pierwszych mieści się w tym zakresie.
Dodaj opcję, by program zapisywał wyniki do pliku pierwsze.txt.

Zadanie 3 – Połącz oba algorytmy
Napisz program, który:

wypisuje wszystkie liczby pierwsze z przedziału,
a potem dla każdej pary sąsiednich liczb pierwszych oblicza ich NWD.

16. Podsumowanie

Algorytm	Co robi	Kluczowa idea
Euklidesa	Szuka największego wspólnego dzielnika	powtarzaj dzielenie, aż reszta = 0
Eratostenesa (sito)	Szuka liczb pierwszych	eliminuj wielokrotności liczb pierwszych

Oba pokazują, że prosty pomysł może być bardziej skuteczny niż złożone wzory.

17. Do zapamiętania

Wielcy matematycy nie mieli komputerów, ale myśleli jak programiści:
krok po kroku, aż do prostego, logicznego rozwiązania.

18. Dla wzrokowców

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

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