Algorytmy Numeryczne na Maturę (NWD, Liczby Pierwsze, Sito) - Zrozum i Zaimplementuj (Python i C++)

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.

Podejście optymalne (maturalne): Pętla do pierwiastka z n

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

Kod - 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 a

Wersja z resztą z dzielenia (optymalna i rekomendowana)

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

Kod - 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;
}

Przykładowe zadanie maturalne z NWD z rozwiązaniem krok po kroku

Poniżej znajdziesz typowe zadanie maturalne z wykorzystaniem algorytmu Euklidesa wraz z pełnym rozwiązaniem.

Zadanie: Znajdź parę liczb o największym NWD

Treść zadania: W pliku dane.txt znajduje się 1000 par liczb naturalnych (w każdym wierszu dwie liczby oddzielone spacją). Znajdź parę liczb, których NWD jest największy i wypisz tę parę oraz wartość NWD.

Krok 1: Zdefiniuj funkcję NWD

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

Krok 2: Wczytaj dane i znajdź maksimum

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

# Wczytaj dane
with open('dane.txt', 'r') as f:
    linie = f.readlines()

# Zmienne do śledzenia maksimum
max_nwd = 0
najlepsza_para = (0, 0)

for linia in linie:
    a, b = map(int, linia.split())
    wynik = nwd(a, b)
    
    if wynik > max_nwd:
        max_nwd = wynik
        najlepsza_para = (a, b)

print(f'Para: {najlepsza_para[0]}, {najlepsza_para[1]}')
print(f'NWD: {max_nwd}')

Wyjaśnienie krok po kroku

1. Definiujemy funkcję NWD - używamy algorytmu Euklidesa z operacją modulo (szybka wersja)
2. Wczytujemy plik - każdy wiersz zawiera parę liczb
3. Przechodzimy przez wszystkie pary - dla każdej liczymy NWD
4. Śledzimy maksimum - jeśli aktualny NWD jest większy, aktualizujemy najlepszą parę
5. Wypisujemy wynik - para liczb i ich NWD

Wskazówka na maturę

Pamiętaj: dwie liczby są względnie pierwsze, gdy ich NWD wynosi 1. Często na maturze pojawia się pytanie typu: 'Ile par w pliku jest względnie pierwszych?' - wystarczy policzyć pary, dla których nwd(a, b) == 1.

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.

1. Test Pierwszości: is_prime(n) – zawsze sprawdzaj dzielniki tylko do sqrt(n).
2. NWD: nwd(a, b) – zawsze używaj optymalnej wersji z resztą z dzielenia (modulo).
3. 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.

Chcesz nauczyć się tego na maturę? Sprawdź nasz kurs do matury z informatyki.