Rozkłada liczbę naturalną na iloczyn liczb pierwszych (faktoryzacja) przez kolejne dzielenia.
Rozkład liczby na czynniki pierwsze to przedstawienie liczby naturalnej jako iloczynu liczb pierwszych. Każda liczba całkowita większa od 1 ma jednoznaczny rozkład (z dokładnością do kolejności).
Przykłady:
24 = 2 · 2 · 2 · 3
60 = 2 · 2 · 3 · 5
Algorytm sprawdza kolejne liczby d zaczynając od 2. Dopóki d dzieli n bez reszty, dopisujemy d do wyniku i dzielimy n przez d. Następnie zwiększamy d o 1 i kontynuujemy. Sprawdzamy tylko do √n – jeśli po tym n > 1, sama wartość n też jest czynnikiem pierwszym.
Na maturze: używany przy obliczaniu NWD, NWW, sumy dzielników i analizie liczb.
funkcja rozklad_pierwszy(n): czynniki ← pusta lista d ← 2 dopóki d * d ≤ n: dopóki n mod d = 0: dodaj d do czynniki n ← n div d d ← d + 1 // jeśli zostało coś większego od 1, to też jest pierwsze jeżeli n > 1: dodaj n do czynniki zwróć czynniki
def rozklad_na_czynniki(n):
czynniki = []
d = 2
while d * d <= n:
while n % d == 0:
czynniki.append(d)
n //= d
d += 1
# jeśli n nadal jest większe od 1, to ostatni czynnik pierwszy
if n > 1:
czynniki.append(n)
return czynniki
# Przykład użycia
print(rozklad_na_czynniki(60))
# Wynik: [2, 2, 3, 5]
print(rozklad_na_czynniki(97))
# Wynik: [97]O(√n)O(log n)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: