Zadania z programowania na maturze z informatyki bardzo często opierają się na przetwarzaniu liczb. Analiza par liczb, szukanie liczb o konkretnych własnościach, badanie podzielności – to wszystko chleb powszedni. Prawie na każdym arkuszu pojawia się zadanie, którego nie da się rozwiązać 'na siłę' i które wymaga znajomości kilku fundamentalnych algorytmów z teorii liczb. Dobra wiadomość jest taka, że tych kluczowych algorytmów jest niewiele, a ich zrozumienie i zapamiętanie gwarantuje Ci cenne punkty. W tym artykule przeprowadzimy Cię przez trzy najważniejsze: sprawdzanie pierwszości, NWD (Algorytm Euklidesa) i Sito Eratostenesa.
1. Sprawdzanie, czy liczba jest pierwsza
Liczba pierwsza to taka liczba naturalna większa od 1, która dzieli się tylko przez 1 i samą siebie (np. 2, 3, 5, 7, 11...). Umiejętność szybkiego sprawdzenia, czy dana liczba `n` jest pierwsza, to absolutna podstawa.
Podejście naiwne: Pętla od 2 do n-1
Pierwsza myśl jest prosta: sprawdźmy po kolei wszystkie liczby od 2 do `n-1`. Jeśli którakolwiek z nich dzieli `n` bez reszty, to znaczy, że `n` ma dodatkowy dzielnik, więc nie jest pierwsza. Jeśli pętla dojdzie do końca i nie znajdzie żadnego dzielnika, liczba jest pierwsza.
Ten algorytm jest poprawny, ale dla dużych liczb (a takie lubią być na maturze, np. rzędu 1 000 000) jest katastrofalnie wolny. Na pewno nie zmieści się w limicie czasu.
Podejście optymalne (maturalne): Pętla do pierwiastka z n
Kluczowa obserwacja jest następująca: jeśli liczba `n` jest złożona (czyli nie jest pierwsza), to można ją przedstawić jako iloczyn `a * b`. Jeśli tak jest, to co najmniej jeden z tych czynników (`a` lub `b`) musi być mniejszy lub równy pierwiastkowi kwadratowemu z `n`. Dlaczego? Bo gdyby oba były większe od `sqrt(n)`, to ich iloczyn `a * b` byłby większy od `n`, co jest sprzeczne. Wystarczy więc szukać dzielników tylko w zakresie od 2 do `sqrt(n)`. Jeśli tam żadnego nie znajdziemy, to 'po drugiej stronie' pierwiastka też na pewno żadnego nie będzie.
Kod - Python (optymalny)
import math
def is_prime(n):
if n < 2:
return False
# Pętla idzie do int(sqrt(n)) włącznie
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
# Przykład użycia
print(is_prime(17)) # True
print(is_prime(100)) # FalseKod - C++ (optymalny)
#include <cmath>
bool is_prime(int n) {
if (n < 2) return false;
for (int i = 2; i <= (int)sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
2. Algorytm Euklidesa (NWD - Największy Wspólny Dzielnik)
NWD dwóch liczb `a` i `b` to największa liczba, która dzieli jednocześnie `a` i `b`. Przykład: NWD(12, 18) = 6. Zadania maturalne często proszą o znalezienie pary liczb o największym NWD lub o skrócenie ułamka (co wymaga NWD licznika i mianownika).
Wersja z odejmowaniem (wolniejsza, ale łatwa do zrozumienia)
Algorytm Euklidesa opiera się na fakcie, że NWD(a, b) = NWD(a-b, b) (zakładając a > b). Możemy więc w pętli odejmować mniejszą liczbę od większej, aż obie liczby będą sobie równe. Ta wspólna wartość to właśnie NWD.
def nwd_sub(a, b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
return aWersja z resztą z dzielenia (optymalna i rekomendowana)
Odejmowanie jest wolne, jeśli liczby bardzo się różnią (np. NWD(1000000, 2)). Można je zastąpić operacją modulo (reszta z dzielenia). Logika opiera się na fakcie, że NWD(a, b) = NWD(b, a % b). Wykonujemy operacje w pętli tak długo, aż `b` osiągnie 0. Ostatnia niezerowa wartość `a` jest odpowiedzią.
Kod - Python (optymalny, iteracyjny)
def nwd_mod(a, b):
while b != 0:
a, b = b, a % b
return a
# Przykład użycia
print(nwd_mod(48, 18)) # 6
print(nwd_mod(121, 11)) # 11Kod - C++ (optymalny, rekurencyjny - często spotykany)
int nwd_mod(int a, int b) {
if (b == 0) {
return a;
}
return nwd_mod(b, a % b);
}
// Wersja iteracyjna (równie dobra)
int nwd_mod_iter(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}3. Sito Eratostenesa (Generowanie liczb pierwszych)
Co jeśli zadanie każe nam znaleźć WSZYSTKIE liczby pierwsze w dużym zakresie, np. od 1 do 1 000 000? Wywoływanie naszej funkcji `is_prime()` milion razy będzie trwało zbyt długo. Potrzebujemy algorytmu, który 'przesieje' cały zakres na raz. Tym właśnie jest Sito Eratostenesa.
Intuicja: 'Wykreślanie' wielokrotności
Wyobraź sobie tabelę ze wszystkimi liczbami od 2 do `n`. Zaczynamy od pierwszej liczby, 2. Wiemy, że jest pierwsza, więc ją zostawiamy, ale 'wykreślamy' z tabeli wszystkie jej wielokrotności (4, 6, 8, 10...). Bierzemy kolejną niewykreśloną liczbę, 3. Jest pierwsza. Wykreślamy jej wielokrotności (6, 9, 12, 15...). Bierzemy kolejną niewykreśloną, 4 - jest już wykreślona. Bierzemy 5. Jest pierwsza. Wykreślamy 10, 15, 20... Kontynuujemy ten proces. Liczby, które na końcu zostaną niewykreślone, to liczby pierwsze.
W implementacji zamiast 'wykreślać', tworzymy tablicę wartości logicznych (boolean) `is_prime` o rozmiarze `n+1`, domyślnie ustawioną na `True`. Następnie 'wykreślanie' polega na ustawianiu `is_prime[k] = False`.
Kod - Python (Sito Eratostenesa)
def sieve(n):
# Tworzymy tablicę boolean, indeksy od 0 do n
# Zakładamy, że wszystkie są pierwsze
primes = [True] * (n + 1)
primes[0] = primes[1] = False # 0 i 1 nie są pierwsze
# Optymalizacja: wystarczy iść do pierwiastka z n
for p in range(2, int(n**0.5) + 1):
# Jeśli p jest nadal 'True', to jest liczbą pierwszą
if primes[p]:
# 'Wykreśl' (ustaw na False) wszystkie wielokrotności p
# Zaczynamy od p*p (bo mniejsze zostały wykreślone przez mniejsze liczby pierwsze)
for i in range(p*p, n + 1, p):
primes[i] = False
# Możemy zwrócić tablicę boolean...
# return primes
# ...albo listę liczb pierwszych
lista_pierwszych = []
for i in range(n + 1):
if primes[i]:
lista_pierwszych.append(i)
return lista_pierwszych
# Przykład: znajdź wszystkie liczby pierwsze do 50
print(sieve(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]Kod - C++ (Sito Eratostenesa)
#include <vector>
std::vector<int> sieve(int n) {
std::vector<bool> primes(n + 1, true);
primes[0] = primes[1] = false;
for (int p = 2; p * p <= n; p++) {
if (primes[p]) {
for (int i = p * p; i <= n; i += p) {
primes[i] = false;
}
}
}
std::vector<int> prime_numbers;
for (int i = 0; i <= n; i++) {
if (primes[i]) {
prime_numbers.push_back(i);
}
}
return prime_numbers;
}
Typowe zadania maturalne wykorzystujące te algorytmy
- "Znajdź liczbę w pliku, która jest liczbą pierwszą i jest najbliższa X." (Wymaga funkcji `is_prime`).
- "Znajdź parę liczb z pliku, których NWD jest największe." (Wymaga funkcji `nwd_mod` w pętli).
- "W ilu wierszach obie liczby są względnie pierwsze?" (Względnie pierwsze = ich NWD wynosi 1. Wymaga `nwd_mod`).
- "Ile liczb z pliku ma co najmniej 3 różne czynniki pierwsze?" (Wymaga sita do wygenerowania listy pierwszych, a potem dzielenia przez nie).
- "Znajdź wszystkie liczby półpierwsze w zakresie..." (Liczba półpierwsza to iloczyn dwóch liczb pierwszych. Wymaga sita).
Podsumowanie - Co musisz zapamiętać?
Te trzy algorytmy to Twój "scyzoryk" do zadań z liczbami. Nie są skomplikowane, ale trzeba je solidnie przećwiczyć, aby pisać je z pamięci pod presją czasu.
- Test Pierwszości: `is_prime(n)` – zawsze sprawdzaj dzielniki tylko do `sqrt(n)`.
- NWD: `nwd(a, b)` – zawsze używaj optymalnej wersji z resztą z dzielenia (modulo).
- Sito Eratostenesa: `sieve(n)` – używaj, gdy musisz znaleźć *wszystkie* liczby pierwsze w dużym zakresie, bo jest o wiele szybsze niż wielokrotne wołanie `is_prime()`.
Opanuj te trzy koncepty, a żadne zadanie z teorii liczb na maturze Cię nie zaskoczy.