#!/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.
        round(-(-n**0.5//1)) to sprytny zapis ceil(sqrt(n)) bez importu math.
        Operator // zawsze zaokrągla w kierunku -infinity, więc najpierw zmieniamy liczbę
        na ujemną, zaokrąglamy w dół, a potem znowu zmieniamy znak, przez co zaokrągliliśmy
        efektywnie w górę. Funkcja round jest tu w zasadzie niepotrzebna, ale dla elegancji
        zamieniamy float (powstały w wyniku działania // na floaty) na int.
        Jeśli ktoś chce bardziej przejrzyście, zawsze może użyć:
        "if i and i<=math.ceil(math.sqrt(n))" oraz "import math".
        """
        if i and i<=round(-(-n**0.5//1)):
            """
            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):
    """
    Poniżej ponownie wykorzystujemy sztuczkę z ograniczeniem przedziału poszukiwania do <=sqrt(n).
    Tym razem używamy dla urozmaicenia metody "dunder" (DoubleUnderscore) obiektu float.
    Do poczytania dla ciekawych. Jak kto woli, ponownie można tam wstawić "math.ceil(math.sqrt(n))", 
    pamiętając o uprzednim "import math".
    """
    liczby=sito_e((n**0.5).__ceil__())
    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))))