Dzielniki do pierwiastka

Sito Eratostenesa i porównanie z metodą naiwną - Informatyka - liceum klasa 1, zakres rozszerzony (Python)

Liczba **pierwsza** ma dokładnie dwa dzielniki: 1 i siebie. Sprawdzanie wszystkich dzielników od 2 do `n - 1` jest wolne. Wystarczy dojść do **pierwiastka** z `n`: jeśli `n = d · e` i `d <= e`, to `d · d <= n`, więc mniejszy dzielnik zawsze znajdziemy wcześniej. Warunek `d * d <= n` nie wymaga liczenia pierwiastka. Program porównuje liczbę sprawdzonych dzielników w obu metodach.

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

n = 1000003
print(n, "pierwsza:", is_prime(n))
print("sprawdzeń do pierwiastka:", int(n ** 0.5) - 1)
print("sprawdzeń do n - 1:", n - 2)

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

Wszystkie lekcje kursu Informatyka - liceum klasa 1, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.