Informatyka. Konkursy i algorytmy
Określanie pierwszości
Do czego służy?
Algorytm do określania pierwszości służy do określenia, czy liczba jest pierwsza, czy nie. Kiedy liczba jest pierwsza? Kiedy dzieli się tylko przez siebie i jeden. Ale jak to sprawdzić? Wydaje się że trzeba sprawdzić wszystkie możliwe liczby mniejsze od danej liczby x.... Czyli złożoność rzędu x... Ale algorytm opisany poniżej wykorzystując pewną własność działa o wiele szybciej!
Algorytm
Dla danej liczy x sprawdzamy wszystkie liczby od 2 do pierwiastka kwadratowego z x.
Jeśli x jest podzielne przez którąś z nich to nie jest liczbą pierwszą. W przeciwnym
wypadku x jest liczbą pierwszą. UWAGA dla 0 i 1 od razu wypisujemy, że nie są pierwsze.
Czemu sprawdzamy tylko do pierwiastka? WYkorzustujemy tu pewną własność dzielników liczb.
Dzielniki liczby x będą się układać parami, dla przykładu dla liczby 12:
1 12, 2 6, 3 4
Zauważmy, że największą możliwą pierwszą liczbą pary będzie
pierwiastek kwadratowy z x - większe liczby będą już drugą liczbą pary. Z tego powodu
sprawdzamy tylko do pierwiastka, ponieważ jeśli tam nie ma dzielników, to dalej też nie
będzie. Tym sposobem przyspieszyliśmy nasz algorytm z O(x) do O(sqrt2(x))
Przykład
Zasymulujmy nasz algorytm na przykładzie dla x = 39(mod to reszta z dzielenia):
sqrt2(39) ≈ 6
39 mod 2 = 1 -> 39 nie jest podzielne przez 2
39 mod 3 = 0 -> 39 jest podzielne przez 3, a więc nie jest liczbą pierwszą. Tutaj
kończymy nasz algorytm.
Implementacja i złożoność
implementacja w c++:int resz;
if(x == 1){
return false;
}
for(int i = 2; i < sqrt(x); i++){
resz = x % i;
if(resz == 0){
return false;
}
}
return true;
}
implementacja w python:
def czy_pierwsza(x):
if(x == 1):
return False
for i in range(2, ceil(sqrt(x))):
resz = x % i
if(resz == 0):
return False
return True
złożoność: