Rozkład liczby na czynniki pierwsze

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

Każdą liczbę większą od 1 da się zapisać jako iloczyn liczb pierwszych. Dzielimy n przez najmniejszy dzielnik tak długo, jak się da, potem próbujemy następnego. Gdy po pętli zostanie coś większego od 1, to też jest czynnik pierwszy.

n = 360
czynniki = []
d = 2
while d * d <= n:
    while n % d == 0:
        czynniki.append(d)
        n //= d
    d += 1
if n > 1:
    czynniki.append(n)
print(czynniki)

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