Sprawdzanie czy liczba jest pierwsza

Liczba pierwsza to absolutny fundament informatyki i kryptografii (np. w algorytmie RSA). Liczba pierwsza to taka liczba całkowita większa od 1, która dzieli się tylko przez 1 i przez samą siebie.

Przykładami liczb pierwszych są: 2, 3, 5, 7, 11, 13, 17... Liczby takie jak 4, 6, 8, 9 to liczby złożone, ponieważ mają więcej niż dwa dzielniki (np. 9 dzieli się przez 1, 3 i 9).

Na maturze często pojawia się zadanie typu "Z podanej listy liczb wypisz tylko te, które są pierwsze". Musimy umieć to zrobić szybko i optymalnie.

Naiwne sprawdzanie (Bardzo powolne)

Pierwszym, co przychodzi na myśl, jest napisanie pętli, która sprawdza wszystkie możliwe dzielniki dla naszej liczby n. Zaczynamy od 2 i sprawdzamy, aż do n - 1. Jeśli jakakolwiek liczba dzieli n bez reszty (reszta % wynosi 0), to n NIE jest pierwsze.

Niestety, dla ogromnych liczb (np. 1 000 000 007) taka pętla wykona miliard obrotów. Złożoność tego rozwiązania to O(n). Na maturze to nie przejdzie ze względu na limit czasu (zazwyczaj 1 sekunda dla C++ i około 2-3 dla Pythona).

Optymalne sprawdzanie – do pierwiastka: O(sqrt(n))

Matematyka przychodzi z pomocą! Jeśli liczba n jest złożona, to na pewno można ją przedstawić w postaci iloczynu dwóch liczb: n = a * b. Zawsze, gdy jeden z dzielników jest większy od pierwiastka z n, to ten drugi musi być mniejszy lub równy pierwiastkowi z n.

[!TIP] Złota zasada: Nie musimy sprawdzać dzielników aż do samej liczby n. Wystarczy sprawdzać maksymalnie do zaokrąglonego w dół pierwiastka z n. Zmniejsza to liczbę operacji dla miliarda z miliarda kroków do... lekko ponad 30 tysięcy! Złożoność takiego algorytmu spada do pierwiastkowej.

Zrozumienie kodu krok po kroku

Oto jak w najprostszy sposób zaimplementować to optymalne rozwiązanie. Zamiast liczyć pierwiastek i bawić się w liczby zmiennoprzecinkowe (co jest wolniejsze), możemy napisać w warunku pętli i * i <= n.

Python

def czy_pierwsza(n):
    # Liczby mniejsze od 2 (np. 0, 1, wartości ujemne) nie są pierwsze
    if n < 2:
        return False
        
    # Zaczynamy szukać dzielnika od 2
    i = 2
    # Sprawdzamy tylko do pierwiastka (i * i <= n)
    while i * i <= n:
        if n % i == 0:     # Jeśli znajdziemy jakikolwiek dzielnik...
            return False   # ...liczba na pewno nie jest pierwsza
        i += 1
        
    # Jeśli pętla się skończyła i nie znaleźliśmy dzielnika, liczba jest pierwsza!
    return True

# Testowanie
print(czy_pierwsza(7))  # True
print(czy_pierwsza(15)) # False

C++

#include <iostream>
using namespace std;

bool czyPierwsza(int n) {
    // Liczby mniejsze od 2 nie są pierwsze
    if (n < 2) return false;
    
    // Pętla od 2 do pierwiastka z n (i * i <= n)
    for (int i = 2; i * i <= n; i++) {
        // Jeżeli reszta z dzielenia wynosi 0, mamy dzielnik
        if (n % i == 0) {
            return false;
        }
    }
    
    // Brak dzielników, liczba jest pierwsza
    return true;
}

int main() {
    cout << czyPierwsza(7) << endl;   // Wypisze 1 (prawda)
    cout << czyPierwsza(15) << endl;  // Wypisze 0 (fałsz)
    return 0;
}

[!IMPORTANT] Dla dociekliwych: Kolejna optymalizacja Oprócz 2, wszystkie inne liczby pierwsze są nieparzyste. Możemy więc jeszcze bardziej przyspieszyć algorytm! Jeśli na samym początku sprawdzimy, czy n dzieli się na 2 i to obsłużymy, możemy rozpocząć pętlę od 3 i skakać od razu co 2 liczby (i += 2). Pomijamy wtedy sprawdzanie wszystkich parzystych liczb (4, 6, 8...), co przyspiesza cały program o kolejne 50%!