Sito Eratostenesa i rozkład na czynniki

🎯 Po co Ci to?

W jednostce 4.1 policzyłeś (zadanie 3), że sprawdzenie pierwszości wszystkich liczb do miliona — każdej z osobna — kosztuje setki milionów operacji. A teraz wyobraź sobie, że potrzebujesz tych liczb naprawdę: do testów kryptograficznych, do zadań maturalnych, do badań. Eratostenes z Cyreny — bibliotekarz Wielkiej Biblioteki Aleksandryjskiej, człowiek, który zmierzył obwód Ziemi patykiem i cieniem — zaproponował 2200 lat temu podejście odwrotne: nie pytaj każdej liczby „czy jesteś pierwsza?", tylko wykreślaj te, które pierwsze być nie mogą. Różnica kosztów zwali Cię z nóg.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• wykonać (ręcznie i w kodzie) sito Eratostenesa i uzasadnić jego poprawność;
• rozłożyć liczbę na czynniki pierwsze algorytmem dzielenia kolejnymi dzielnikami;
• wyjaśnić, dlaczego mnożenie jest łatwe, a rozkład trudny — i czemu to ważne dla świata.

🔁 Przypomnij sobie

Z 3.4: lista i indeksy; z 4.1: dzielnik nie większy niż $\sqrt{n}$; z 1.5: koszt liczymy dla całości zadania, nie pojedynczej operacji.

📘 Wyjaśnienie

Pomysł sita. Wypisz wszystkie liczby od 2 do $n$. Najmniejsza niewykreślona — 2 — jest pierwsza; wykreśl jej wielokrotności (4, 6, 8, …), bo skoro dzielą się przez 2, pierwsze nie są. Następna niewykreślona — 3 — jest pierwsza (nic mniejszego jej nie wykreśliło, więc nie ma mniejszych dzielników!); wykreśl 6, 9, 12, … I tak dalej. Co zostanie na płótnie, to czyste złoto: same pierwsze.

W kodzie tablica wartości logicznych gra rolę papieru, a False — skreślenia:

def sito(n):
    pierwsza = [True] * (n + 1)        # indeksy 0..n; na start wszyscy "niewykreśleni"
    pierwsza[0] = pierwsza[1] = False  # 0 i 1 poza konkursem
    p = 2
    while p * p <= n:                  # wykreślać wystarczy do pierwiastka (4.1!)
        if pierwsza[p]:                # p przeżyło = jest pierwsze
            w = p * p                  # start od p², nie od 2p — patrz 💭
            while w <= n:
                pierwsza[w] = False
                w = w + p
        p = p + 1
    return [i for i in range(2, n + 1) if pierwsza[i]]   # zbierz ocalałych

(Ostatnia linijka to skrócony zapis pętli budującej listę — czytaj: „wszystkie $i$ od 2 do $n$, dla których pierwsza[i]". Wolno Ci też napisać zwykłą pętlę z append — to identyczne.)

💭 Pomyśl: Dlaczego wykreślanie wielokrotności liczby $p$ można zacząć od $p^2$, a nie od $2p$? Sprawdź na przykładzie $p = 7$: kto już wykreślił 14, 21, 28, 35, 42?

Sprawdź odpowiedź

$14 = 2 \cdot 7$ wykreśliła dwójka, $21 = 3 \cdot 7$ — trójka, $28$ — dwójka, $35 = 5 \cdot 7$ — piątka, $42$ — dwójka. Każda wielokrotność $k \cdot p$ z $k < p$ ma dzielnik mniejszy od $p$ — więc padła we wcześniejszych turach. Pierwsza „świeża" ofiara siódemki to $7^2 = 49$. Stąd też warunek p * p <= n: gdy $p^2$ wyskakuje poza tablicę, nie ma już czego wykreślać.

Ile to kosztuje? Dwójka wykreśla $n/2$ liczb, trójka $n/3$, piątka $n/5$… Suma tych ułamków rośnie bardzo powoli — dla $n$ = milion łączny koszt to około kilku milionów prostych operacji, ułamek sekundy. Porównaj z miliardami z zadania 4.1/3: sito jest setki razy szybsze, bo dzieli pracę mądrze — żadna liczba złożona nie jest „badana", każda jest po prostu raz (no, czasem parę razy) skreślana. Cena: pamięć na całą tablicę — sito musi widzieć wszystkie liczby naraz. Wymiana „pamięć za czas" to jeden z wielkich handli algorytmiki; jeszcze go spotkasz.

Rozkład na czynniki pierwsze. Sito daje listę pierwszych; rozkład odpowiada na pytanie odwrotne — z czego złożona jest dana liczba. Algorytm: dziel przez najmniejsze co się da, aż zostanie 1:

def rozklad(n):
    czynniki = []
    d = 2
    while d * d <= n:
        while n % d == 0:          # dziel, póki d dzieli (czynnik może się powtarzać!)
            czynniki.append(d)
            n = n // d
        d = d + 1
    if n > 1:                      # to, co przetrwało, jest pierwsze
        czynniki.append(n)
    return czynniki

rozklad(360) → dwójki: 360→180→90→45; trójki: 45→15→5; pętla staje ($d^2 > 5$), zostało 5 → [2, 2, 2, 3, 3, 5]. Czyli $360 = 2^3 \cdot 3^2 \cdot 5$ — dokładnie ten zapis, którym w szkole liczyłeś NWD „metodą rozkładu". Zauważ wewnętrzne while: czynnik wyciągamy do skutku, inaczej po jednej dwójce pobiegalibyśmy do trójki, zostawiając 90 niedokończone.

A teraz rzecz najważniejsza w tej jednostce. Pomnożyć dwie liczby pierwsze po 300 cyfr — mikrosekundy. Dostać ich iloczyn i odzyskać czynniki — naszym algorytmem: $d$ biegnie do $\sqrt{n}$, czyli $10^{300}$ kroków. Dłużej, niż istnieje wszechświat. I nikt — mimo stuleci prób — nie zna zasadniczo szybkiej metody. Ta asymetria (mnożenie łatwe, rozkład beznadziejny) wygląda na wadę… a jest fundamentem: na niej stoi kryptografia klucza publicznego, którą poznasz w 5.7. Czasem to, czego nie umiemy policzyć, jest cenniejsze od tego, co umiemy.

⚠️ Uwaga, pułapka

W rozkładzie nie zapomnij końcówki if n > 1. Bez niej rozklad(26) zwróci [2] i zgubi trzynastkę: pętla staje przy $d^2 > 13$, a ocalałe $n = 13$ nikt nie dopisze. To brzeg z gatunku „duży czynnik pierwszy na końcu" — testuj na liczbach typu $2 \cdot 13$, $3 \cdot 17$, i na czystych pierwszych (rozkład = ona sama).

🛠️ Teraz Ty

Bez komputera: wykonaj sito na kartce dla $n = 30$ (tabelka 2–30, skreślaj kolejno) i rozłóż 504. Z komputerem: uruchom sito(1000) — ile jest pierwszych do tysiąca? (Powinno wyjść 168.) Potem porównaj czasy: sito do miliona kontra pętla wywołująca pierwsza(k) z 4.1 dla wszystkich $k$ — zmierz oba podejścia i zapisz wynik; takie liczby lepiej raz zobaczyć niż sto razy usłyszeć.

📐 Definicje tej lekcji

• Sito Eratostenesa — wszystkie pierwsze do $n$ przez wykreślanie wielokrotności; start skreślania od $p^2$, główna pętla do $\sqrt{n}$.
• Rozkład na czynniki pierwsze — dzielenie przez kolejne $d$ do skutku, do $\sqrt{n}$; ocalałe $n > 1$ jest ostatnim czynnikiem.

📌 Najważniejsze w pigułce

• Sito odwraca pytanie: zamiast badać pierwszość, wykreśla złożone — i dlatego jest setki razy szybsze od testowania po kolei.
• Rozkład: wyciągaj czynnik do skutku, nie zgub dużego czynnika na końcu.
• Mnożenie łatwe, rozkład (praktycznie) niemożliwy — ta asymetria to skarb, nie usterka: strzeże internetu.

🎒 Zadania

1. Wykonaj sito dla $n = 50$ i wypisz pierwsze. Których liczb NIE wykreśliła żadna z: 2, 3, 5, 7 — i dlaczego to już koniec pracy?

Wskazówka i odpowiedź

Pierwsze do 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Po siódemce następna niewykreślona to 11, ale $11^2 = 121 > 50$ — każda złożona do 50 ma dzielnik $\le \sqrt{50} \approx 7{,}1$, więc już poległa. Cztery tury skreślania załatwiają pięćdziesiąt liczb; do miliona wystarczy 168 tur (pierwsze do tysiąca) — praca rośnie zdumiewająco wolno.

2. Użyj rozkładu do policzenia $\text{NWD}(360, 300)$ i $\text{NWW}(360, 300)$ metodą szkolną (wspólne czynniki / wszystkie czynniki), a potem sprawdź Euklidesem z 4.2. Kiedy która metoda ma sens?

Wskazówka i odpowiedź

$360 = 2^3 \cdot 3^2 \cdot 5$, $300 = 2^2 \cdot 3 \cdot 5^2$. NWD: wspólne w najniższych potęgach $= 2^2 \cdot 3 \cdot 5 = 60$; NWW: wszystkie w najwyższych $= 2^3 \cdot 3^2 \cdot 5^2 = 1800$. Euklides: $(360,300) \to (300,60) \to (60,0)$ — NWD 60 ✓. Rozkład daje wgląd w budowę liczb (i ładnie uczy), Euklides — szybkość bez żadnego wglądu. Do rachunków bierz Euklidesa; do zrozumienia — rozkład.

3. Zmodyfikuj rozklad, by zwracał pary (czynnik, wykładnik), np. rozklad2(360) → [(2,3), (3,2), (5,1)]. Wykorzystaj wynik do policzenia liczby dzielników liczby 360.

Wskazówka i odpowiedź

Zamiast append(d) w wewnętrznym while — licz ile i po pętli dopisz (d, ile). Liczba dzielników: każdy dzielnik wybiera wykładnik dwójki (0–3: cztery opcje), trójki (0–2: trzy), piątki (0–1: dwie) — $(3+1)(2+1)(1+1) = 24$ dzielniki. Rozkład to „DNA liczby": z par (czynnik, wykładnik) odczytasz dzielniki, ich liczbę i sumę bez żadnego dzielenia.

🔍 Sprawdź, czy umiesz

• Wykonać sito ręcznie i uzasadnić start skreślania od $p^2$.
• Rozłożyć liczbę na czynniki kodem i nie zgubić ostatniego czynnika.
• Opowiedzieć, na czym polega asymetria mnożenie/rozkład i gdzie pracuje.

---