def descompune_in_factori_primi(n):
    factori = []
    divisor = 2

    while n > 1:
        count = 0
        while n % divisor == 0:
            n //= divisor
            count += 1
        if count > 0:
            factori.append((divisor, count))
        divisor += 1
        # Optimizare: verificăm doar până la √n
        if divisor * divisor > n:
            if n > 1:
                factori.append((n, 1))
            break

    return factori

def main():
    try:
        numar = int(input("Introduceti un numar: "))
    except ValueError:
        print("Va rugam sa introduceti un numar valid!")
        return

    if numar <= 1:
        print("Numarul trebuie sa fie mai mare decat 1!")
        return

    factori = descompune_in_factori_primi(numar)

    print("Descompunerea in factori primi este: ", end="")
    for i, (base, exponent) in enumerate(factori):
        print(f"{base}^{exponent}", end="")
        if i < len(factori) - 1:
            print(" * ", end="")
    print()

if __name__ == "__main__":
    main()