Rozkład liczby na czynniki pierwsze w Pythonie czyli faktoryzacja liczby

powrót

Faktoryzacja liczby, czyli rozłożenie liczby na czynniki pierwsze jest jednym z tych zagadnień maturalnych, który sprawia sporo problemów. Algorytm łatwo jest napisać w wersji nieoptymalnej i stracić punkty na maturze. Wzorcowa złożoność tego algorytmu jest $$O(\sqrt(n)),$$gdzie n to rozkładana liczba. Rozłożenie liczby na czynniki pierwsze, inaczej faktoryzacja tej liczby, polega na przedstawieniu jej w postaci iloczynu liczb pierwszych. Idea algorytmu jest prosta.

• Najmniejszy możliwy czynnik pierwszy to liczba 2, ponieważ jest to najmniejsza liczba pierwsza i taką wartość początkową ustawiamy dla zmiennej czynnik (*),
• algorytm wykonujemy tak długo, jak długo $$czynnik \cdot czynnik <= liczba,$$i to jest najważniejsza zarówno, jak i najtrudniejsza do zrozumienia część algorytmu. Zauważ, że sprawdzasz kolejne iteracje zmiennej czynnik (**), czy są one dzielnikiem zmiennej liczba (****). Zmienna czynnik przyjmuje wartości 2, 3, 4, 5, 6, 7, ... Widzimy, że nie wszystkie z wypisanych liczb są pierwsze: 4, 6, ale tak naprawdę nigdy nie będą one brane pod uwagę, ponieważ każda z nich rozkłada się na czynniki, które wystąpiły wcześniej:$$4 = 2\cdot 2$$$$6 = 2\cdot 3,$$patrz linijka kodu (***).
• Program kończymy, gdy nie będzie spełniony warunek $$czynnik*czynnik <= liczba.$$
• jeżeli zmienna czynnik < 1, to jej wartość musi być liczbą pierwszą, więc należy ją także wypisać # (*****).

Poniżej znajduje się program, rozkłada wczytaną liczbę naturalną większą od 1 na czynniki pierwsze.

#*****************www.algorytm.edu.pl****************
def faktoryzacja(liczba):
    czynnik = 2 # (*)
    while czynnik*czynnik <= liczba:
        while liczba % czynnik == 0: # (****)
            print(czynnik, end=' ')
            liczba = liczba//czynnik # (***)
        czynnik += 1 # (**)
    if liczba > 1:
        print(liczba) # (*****)

# --------blok główny programu -----------

liczba = int(input())
faktoryzacja(liczba)