Sprawdza czy podana liczba jest pierwsza – ma dokładnie dwa dzielniki: 1 i samą siebie.
Liczba pierwsza to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie. Przykłady: 2, 3, 5, 7, 11, 13.
Naiwny algorytm sprawdzałby wszystkie liczby od 2 do n - 1. Zoptymalizowana wersja wykorzystuje dwie obserwacje:
Po pierwsze, jeśli liczba n ma dzielnik większy od √n, to musi mieć też dzielnik mniejszy od √n. Wystarczy więc sprawdzić dzielniki do pierwiastka z n, co redukuje złożoność z O(n) do O(√n).
Po drugie, po wykluczeniu parzystości na początku, sprawdzamy tylko dzielniki nieparzyste (krok co 2).
Na maturze: bardzo częsty algorytm, używany jako podprogram w wielu zadaniach (rozkład na czynniki, sito, NWD).
funkcja czy_pierwsza(n): jeżeli n < 2: zwróć fałsz jeżeli n = 2: zwróć prawda jeżeli n mod 2 = 0: zwróć fałsz // sprawdzamy tylko nieparzyste dzielniki do √n i ← 3 dopóki i * i ≤ n: jeżeli n mod i = 0: zwróć fałsz i ← i + 2 zwróć prawda
def czy_pierwsza(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
# Przykład użycia
print(czy_pierwsza(17))
# Wynik: True
print(czy_pierwsza(15))
# Wynik: False
print(czy_pierwsza(2))
# Wynik: True#include <iostream>
using namespace std;
bool czy_pierwsza(long long n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (long long i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
int main() {
cout << czy_pierwsza(17) << "\n"; // 1
cout << czy_pierwsza(15) << "\n"; // 0
cout << czy_pierwsza(2) << "\n"; // 1
}O(√n)O(1)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: