Czy liczba jest pierwsza: dzielniki do pierwiastka

Liczby pierwsze i sito Eratostenesa - Algorytmy z podstawy programowej (Python)

**Liczba pierwsza** ma dokładnie dwa dzielniki: 1 i samą siebie (2, 3, 5, 7, 11...). Liczba 1 nie jest pierwsza. Nie trzeba sprawdzać wszystkich dzielników aż do n. Jeśli n = a * b, to jeden z czynników jest nie większy niż pierwiastek z n. Wystarczy więc sprawdzać d, dopóki `d * d <= n`. Dla n = 97 to tylko dzielniki 2..9 zamiast 2..96.

def czy_pierwsza(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True


for n in [1, 2, 9, 17, 91, 97]:
    print(n, czy_pierwsza(n))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy z podstawy programowej·Zaloguj się, aby zapisać postęp na koncie.