Python: Sprawdzanie czy liczba jest liczbą pierwszą

Aby sprawdzić, czy liczba jest liczbą pierwszą, należy sprawdzić czy posiada ona dzielniki inne niż 1 i samą siebie.

Należy pamiętać, że 0 i 1 nie są liczbami pierwszymi, natomiast 2 jest liczbą pierwszą.

Algorytm

Zwraca True jeśli liczba jest pierwsza, zwraca False jeśli nie jest.

def czy_pierwsza(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False

    pierw = int(n**0.5) + 1
    for dzielnik in range(3, pierw, 2):
        if n % dzielnik == 0:
            return False
    return True

Opis działania

Najpierw algorytm sprawdza czy wprowadzona liczba jest dwójką. Liczba 2 to wyjątek - musimy ją sprawdzić, ponieważ jest to jedyna liczba pierwsza, która jest parzysta. Jeśli to dwójka, to liczba jest pierwsza.
if n % 2 == 0 or n <= 1 - jeśli liczba jest parzysta lub mniejsza bądź równa 1, to na pewno nie jest pierwsza.
Następnie algorytm sprawdza czy wprowadzona liczba posiada dzielniki. Jeśli tak, to nie jest to liczba pierwsza, a jeżeli nie, to jest to liczba pierwsza.

Algorytm sprawdza dzielniki z przedziału \([3, \lfloor\sqrt{n}\rfloor+1 )\), gdzie \( \lfloor \sqrt{n} \rfloor \) to pierwiastek z n zaokrąglony w dół.
Algorytm mógłby sprawdzać dzielniki z przedziału \([3, n)\), jednak jest to nadmiarowy przedział który jedynie spowalniałby algorytm, szczególnie przy większych liczbach.

Więc skąd ten przedział? Dzielniki zawsze występują parami. Każdy dzielnik z przedziału \([3, \lfloor\sqrt{n}\rfloor+1)\) będzie odpowiadał jednemu z przedziału \([\lfloor\sqrt{n}\rfloor+1, n)\). Można więc zatem bezpiecznie sprawdzić w algorytmie jedynie dzielniki z przedziału \([3, \lfloor\sqrt{n}\rfloor+1 )\).