Czy liczba jest pierwsza?

🎯 Po co Ci to?

Za każdym razem, gdy Twoja przeglądarka pokazuje kłódkę przy adresie banku, gdzieś w tle pracują liczby pierwsze — i to nie byle jakie, tylko po kilkaset cyfr. Zanim w dziale 5 zobaczysz, jak liczby pierwsze chronią Twoje pieniądze, musisz umieć odpowiedzieć na pytanie znacznie skromniejsze: jak w ogóle sprawdzić, czy liczba jest pierwsza? Odpowiedź naiwna jest łatwa. Odpowiedź dobra — nauczy Cię jednej z najważniejszych sztuczek algorytmiki: nie sprawdzaj tego, co już wiesz.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• napisać test pierwszości sprawdzający dzielniki i uzasadnić jego poprawność;
• przyspieszyć go, ograniczając sprawdzanie do $\sqrt{n}$ — i wyjaśnić, dlaczego to wystarcza;
• obsłużyć przypadki brzegowe: 0, 1, 2, liczby parzyste.

🔁 Przypomnij sobie

Z 3.2: n % d == 0 znaczy „$d$ dzieli $n$ bez reszty". Z 3.3: pętla + licznik. Z 1.5: koszt algorytmu liczymy liczbą obrotów pętli.

📘 Wyjaśnienie

📐 DEFINICJA — liczba pierwsza: liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie.

Po ludzku: liczba, której nie da się „rozłożyć" na mnożenie mniejszych liczb naturalnych (większych od 1). Czym NIE jest: jedynka liczbą pierwszą nie jest — ma tylko jeden dzielnik, a definicja żąda dwóch. To nie kruczek: matematyka wyklucza 1, żeby każda liczba miała jednoznaczny rozkład na czynniki pierwsze (o tym w 4.4).

Podejście wprost. Skoro pierwsza = bez dzielników poza 1 i sobą, to sprawdźmy wszystkich kandydatów:

def pierwsza(n):
    if n < 2:
        return False
    for d in range(2, n):          # kandydaci: 2, 3, ..., n-1
        if n % d == 0:
            return False           # znaleziony dzielnik — koniec, nie pierwsza
    return True                    # przeżyliśmy całą pętlę — pierwsza

Zwróć uwagę na dwa szczegóły rzemiosła. Warunek n < 2 na początku załatwia brzegi (0, 1 i liczby ujemne) zanim pętla zdąży cokolwiek zepsuć. A return False w środku pętli to natychmiastowa ewakuacja: po znalezieniu pierwszego dzielnika dalsze sprawdzanie jest stratą czasu.

💭 Pomyśl: Ile obrotów pętli wykona ten test dla $n = 1,000,003$ (to liczba pierwsza)? A gdyby $n$ miało 18 cyfr?

Obcięcie do pierwiastka. Kluczowa obserwacja: dzielniki chodzą parami. Jeśli $d$ dzieli $n$, to $n/d$ też dzieli $n$: dla $n = 36$ pary to $(2, 18)$, $(3, 12)$, $(4, 9)$, $(6, 6)$. W każdej parze jeden z dzielników jest nie większy niż $\sqrt{n}$ — bo gdyby obydwa były większe od $\sqrt{36} = 6$, ich iloczyn przekroczyłby 36. Wniosek: jeśli $n$ ma jakikolwiek dzielnik, to ma też dzielnik nie większy od $\sqrt{n}$. Wystarczy więc sprawdzać do pierwiastka:

def pierwsza(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:              # zamiast d <= sqrt(n): bez ułamków!
        if n % d == 0:
            return False
        d = d + 1
    return True

Warunek d * d <= n to elegancki unik: porównujemy $d^2$ z $n$ zamiast $d$ z $\sqrt{n}$, więc zostajemy w bezpiecznym świecie liczb całkowitych (pamiętasz z 2.4, czemu ułamków lepiej unikać w porównaniach?).

Ile zyskaliśmy? Dla miliona: było milion obrotów, jest tysiąc. Dla $10^{18}$: było 30 lat, jest sekunda. Jedna obserwacja matematyczna dała przyspieszenie miliardkrotne — to jest dokładnie to, co w 1.5 obiecywał Gauss: najlepsze algorytmy wygrywają pomysłem, nie sprzętem.

🧮 Prześledź

Prześledź pierwsza(91) — uzupełnij tabelkę. (91 wygląda na pierwszą, prawda?)

⚠️ Uwaga, pułapka

Najczęstszy błąd w teście z pierwiastkiem: warunek d * d < n zamiast <=. Różnica ujawnia się dla kwadratów liczb pierwszych: dla $n = 49$ pętla z < zatrzyma się na $d = 6$ (bo $49 < 49$ jest fałszem... nie — $6 \cdot 6 = 36 < 49$ jeszcze przejdzie, ale $7 \cdot 7 = 49 < 49$ już nie) i nigdy nie sprawdzi $d = 7$ — a 49 dzieli się właśnie przez 7. Wynik: „49 jest pierwsze". Dane brzegowe dla tego algorytmu to kwadraty liczb pierwszych: 4, 9, 25, 49, 121 — miej je w zestawie testów zawsze.

🌍 Powiązania

„Sprawdzaj tylko do $\sqrt{n}$, resztę znasz z par" spotkałeś już w zadaniu o dzielnikach (3.3) — a schemat „wykorzystaj symetrię, żeby liczyć połowę" wróci przy min-maksie (dział 6). Matematyka dostarcza tu twierdzenie, informatyka zamienia je w przyspieszenie: to modelowa współpraca, o której mówi rozszerzenie podstawy (rola pojęć matematycznych w projektowaniu algorytmów).

🛠️ Teraz Ty

Bez komputera: rozstrzygnij testem z pierwiastkiem, czy pierwsze są: 97, 111, 143. (Dla każdej wypisz, które $d$ sprawdzasz.) Z komputerem: zaprogramuj obie wersje i zmierz różnicę — pętla sprawdzająca pierwszość wszystkich liczb do 100 000 wersją naiwną i sprytną (czas zmierzysz, opakowując pętlę w odczyty zegara; w Pythonie import time, time.time() przed i po).

📐 Definicje tej lekcji

• Liczba pierwsza — naturalna, > 1, o dokładnie dwóch dzielnikach.
• Test dzielników do $\sqrt{n}$ — pierwszość sprawdza się pętlą while d*d <= n; dzielniki chodzą parami, więc mniejszy z pary nie przekracza pierwiastka.

📌 Najważniejsze w pigułce

• 1 nie jest pierwsze; brzegi (0, 1, 2, kwadraty pierwszych) testuj zawsze.
• Dzielniki chodzą parami — dlatego wystarczy sprawdzać do $\sqrt{n}$: z miliona obrotów robi się tysiąc.
• d * d <= n zamiast porównań z pierwiastkiem: całkowite, bez błędów zaokrągleń, z równością!

🎒 Zadania

1. Które liczby są pierwsze: 101, 111, 121, 131? Dla każdej niepierwszej podaj rozkład.

2. Ulepsz test: po sprawdzeniu $d = 2$ kolejne parzyste $d$ nie mają sensu (skoro 2 nie dzieli $n$, to 4, 6, 8… tym bardziej). Przepisz pętlę tak, by po dwójce sprawdzała tylko nieparzyste. Ile obrotów oszczędzasz?

if n % 2 == 0:
    return n == 2          # jedyna parzysta pierwsza!
d = 3
while d * d <= n:
    if n % d == 0:
        return False
    d = d + 2              # krok co 2: tylko nieparzyste

3. Funkcja pierwsza dostaje kolejno wszystkie liczby od 2 do $n$ (tak policzylibyśmy „wszystkie pierwsze do $n$"). Oszacuj łączny koszt dla $n = 1,000,000$ i zanotuj wynik — w jednostce 4.4 porównasz go z sitem.

🔍 Sprawdź, czy umiesz

• Wyjaśnić parą dzielników, czemu wystarczy sprawdzać do $\sqrt{n}$.
• Wskazać dane brzegowe testu pierwszości i powiedzieć, co psuje < zamiast <=.
• Napisać test z pamięci — z ewakuacją return False w środku pętli.