Dzielniki tylko do pierwiastka

Rozkład liczby na czynniki pierwsze - Algorytmy: zakres rozszerzony (Python)

Jeśli liczba n nie ma dzielnika d spełniającego d * d <= n, to jest pierwsza. Wystarczy więc sprawdzać dzielniki do pierwiastka, a to, co zostanie na końcu (większe od 1), jest ostatnim czynnikiem pierwszym. Dla dużych liczb pierwszych to ogromna oszczędność czasu.

def factorize(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors


for number in [84, 97, 1001, 2026]:
    print(number, "=", " * ".join(str(f) for f in factorize(number)))

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

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.