#!/usr/bin/python3
"""
Prosta implementacja sita Eratostenesa do znajdowania liczb pierwszych oraz jego wykorzystanie do rozkładu liczby na czynniki pierwsze.
"""

def sito_e(n):
    """
    Sito Eratostenesa. Tworzymy tablicę liczb i "wykreślamy" (zaznaczamy jako False) wszystkie będące
    wielokrotnościami jakiejś liczby -- czyli liczby złożone (nie-pierwsze). Te, które przetrwają, 
    niechybnie muszą być pierwsze.
    """
    pierwsze=list(range(n+1))
    """
    Jedynka (o ironio) z definicji nie jest pierwsza. Zero zresztą też, ale Python automatycznie interpretuje 0 (int) jako False.
    """
    pierwsze[1]=False
    for i in pierwsze:
        """
        Nie musimy sprawdzać wszystkich liczb, bo jeśli liczba się wyraża
        przez l=a*b, to jedno z {a,b} zawsze będzie <= sqrt(n).
        Test (if i) wyklucza nam też ze sprawdzania liczby wykreślone
        dotychczas.
        """
        if i and i*i <=n:
            """
            Wykreślamy wielokrotności i. Należałoby więc zacząć od mult=2*i.
            Jednakże jeżeli dla liczb <=i*i istniała jakaś liczba złożona, to musiała już
            mieć czynniki < sqrt(i*i)=i, więc zostać wykreślona. Startujemy zatem od tego miejsca.
            """
            mult=i*i
            while mult<=n:
                pierwsze[mult]=False
                mult+=i
    return [i for i in pierwsze if i]


def rozklad(n):
    liczby=sito_e(int(n**0.5))
    czynniki=[]
    for i in liczby:
        while n % i == 0:
            czynniki.append(i) #Znaleźliśmy czynnik pierwszy
            n //= i #Operujemy dalej na pozostałości
    if n!=1: #Mogło nam na koniec zostać 1, ale to nie liczba pierwsza
        czynniki.append(n) #Przypadek, gdy n jest liczbą pierwszą i się (dalej lub wcale) nie rozkłada
    return czynniki

n=int(input("Podaj liczbę: "))
print("Liczby pierwsze <= n:",sito_e(n))
print("Rozkład liczby: "+str(n)+" = "+" * ".join(map(str,rozklad(n))))