I Liceum Ogólnokształcące w Jarosławiu - Informatyka
Informatyka · I LO · Klasa II

Liczby pierwsze i funkcje w Pythonie

Od sita Eratostenesa po algorytm z pierwiastkiem. Poznaj, jak matematyka i programowanie łączą się w jedno.

1 Liczby złożone i pierwsze

Dodatnie liczby naturalne większe od 1, które można przedstawić jako iloczyn dwóch mniejszych liczb naturalnych, nazywamy liczbami złożonymi. Przykłady: 9 = 3·3, 10 = 2·5, 42 = 2·3·7.

Pozostałe liczby (poza 1) to liczby pierwsze – podzielne wyłącznie przez 1 i same siebie. Np. 2, 3, 5, 7, 11, 13, 17, 19…

Liczba 1 nie jest ani pierwsza, ani złożona – to wyjątek. Liczba 2 jest jedyną parzystą liczbą pierwszą.
Rozkłady na czynniki
36 = 2 · 2 · 3 · 3
100 = 2 · 2 · 5 · 5
42 = 2 · 3 · 7
87 = 3 · 29
186 = 2 · 3 · 31
Kluczowy fakt

Jeśli liczba n jest złożona, to przynajmniej jeden z jej czynników jest mniejszy lub równy √n. Dlatego wystarczy sprawdzać dzielniki tylko do √n!

2 Zastosowania w kryptografii

Liczby pierwsze są fundamentem nowoczesnej kryptografii (np. algorytmu RSA — od nazwisk twórców: Rivest, Shamir, Adleman, MIT 1977). Bezpieczeństwo szyfrowania polega na prostym fakcie matematycznym: łatwo jest pomnożyć dwie duże liczby pierwsze, ale praktycznie niemożliwe jest wykonanie operacji odwrotnej — czyli rozkład ich iloczynu z powrotem na czynniki. Dla liczb rzędu 150 cyfr nawet najpotężniejsze współczesne komputery potrzebowałyby miliardów lat.

Przykład (uproszczony)
104 729 × 15 013 = 1 571 817 677  →  łatwe
1 571 817 677 = ? × ?            →  bardzo trudne

RSA używa dwóch kluczy: publicznego (znany wszystkim, służy do szyfrowania) i prywatnego (tylko odbiorca może odszyfrować wiadomość). To jak otwarta skrzynka pocztowa przed domem — każdy może włożyć list, ale tylko właściciel ma klucz do skrzynki.

RSA jest używany praktycznie wszędzie w internecie: połączenia HTTPS (kłódka w przeglądarce), bankowość elektroniczna, podpisy cyfrowe i szyfrowane e-maile. Zagrożeniem dla RSA są komputery kwantowe, które mogłyby znacznie przyspieszyć faktoryzację — dlatego już teraz trwają prace nad kryptografią postkwantową.

2 Sito Eratostenesa – animacja krok po kroku

Algorytm skreśla wielokrotności każdej liczby pierwszej. Liczby, które przetrwają, są pierwsze. Kliknij Następny krok lub Auto, by obserwować działanie dla liczb 1–100.

liczba pierwsza
aktualnie przetwarzana
skreślona (złożona)
3 Trzy algorytmy – porównanie

Algorytm 1: Najprostszy test (sprawdza od 2 do n−1)

def CzyPierwsza_v1(n):
    for i in range(2, n):
        if n % i == 0:
            return 0  # znaleziono dzielnik
    return 1   # brak dzielnika → pierwsza
Dla n = 1 000 001 wykonuje nawet milion dzieleń. Bardzo wolny dla dużych liczb.

Algorytm 2: Ulepszony – z pierwiastkiem i krokiem 2

from math import sqrt

def CzyPierwsza_v2(n):
    if n == 2: return 1
    if n % 2 == 0: return 0  # parzyste > 2 są złożone
    pierwiastek = int(sqrt(n))
    for i in range(3, pierwiastek+1, 2):
        if n % i == 0: return 0
    return 1
Krok 2 → sprawdzamy tylko nieparzyste. Zatrzymuje się na √n. Dla n = 1 000 001 wykonuje ok. 500 dzieleń – tysiąckrotnie szybszy!

Kompletny program – definicja funkcji + wywołanie

Sama definicja funkcji (def CzyPierwsza_v2...) nie daje żadnego widocznego efektu – to tylko „przepis". Aby program coś zrobił, trzeba funkcję wywołać, czyli użyć jej w kodzie głównym.
from math import sqrt

# ── definicja funkcji ──────────────────────
def CzyPierwsza_v2(n):
    if n == 2: return 1
    if n % 2 == 0: return 0
    pierwiastek = int(sqrt(n))
    for i in range(3, pierwiastek+1, 2):
        if n % i == 0: return 0
    return 1

# ── wywołanie funkcji (program główny) ─────
liczba = int(input("Podaj liczbę: "))

if CzyPierwsza_v2(liczba) == 1:
    print("Liczba pierwsza")
else:
    print("Liczba złożona")
Przykładowe uruchomienie:
Podaj liczbę: 97
Liczba pierwsza

Podaj liczbę: 100
Liczba złożona

Wywołanie dla wielu liczb jednocześnie

from math import sqrt

def CzyPierwsza_v2(n):
    if n == 2: return 1
    if n % 2 == 0: return 0
    pierwiastek = int(sqrt(n))
    for i in range(3, pierwiastek+1, 2):
        if n % i == 0: return 0
    return 1

# wywołanie dla listy liczb
for n in [2, 9, 11, 15, 97, 100]:
    if CzyPierwsza_v2(n) == 1:
        print(n, "– pierwsza")
    else:
        print(n, "– złożona")
Wynik:
2 – pierwsza
9 – złożona
11 – pierwsza
15 – złożona
97 – pierwsza
100 – złożona

Porównanie liczby operacji

Moduł math to plik .py z gotowymi funkcjami matematycznymi. Importujemy go instrukcją from math import sqrt. Zawiera też: sin, cos, log, factorial i wiele innych.
4 Sprawdź dowolną liczbę
5 Ćwiczenia sprawdzające