Dzielenie przez kolejne dzielniki

Rozkład liczby na czynniki pierwsze - Informatyka - liceum klasa 1, zakres rozszerzony (Python)

Każdą liczbę naturalną `n > 1` da się zapisać jako iloczyn liczb pierwszych, i to jednoznacznie (z dokładnością do kolejności). Algorytm: dziel `n` przez `d = 2, 3, 4, ...`, dopóki się dzieli, zapisując `d`. Wystarczy sprawdzać `d` do `√n`: jeśli po pętli zostało `n > 1`, jest ono liczbą pierwszą i ostatnim czynnikiem. Dzielniki złożone (4, 6) nigdy nie dzielą, bo ich czynniki usunięto wcześniej.

n = 360
m = n
d = 2
while d * d <= m:
    while m % d == 0:
        print(m, "|", d)
        m //= d
    d += 1
if m > 1:
    print(m, "|", m)
    m = 1
print(m)

Ł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.