N = 10**5

is_prime = lambda n: n > 1 and all(n % i != 0
                                   for i in range(2,
                                                  int(n**0.5) + 1))

primes = [i for i in range(2, N) if is_prime(i)]


def decompose(n):
    if n > N**2:
        return  # si n > N^2, on n'est pas assuré du résultat
    else:
        dec = []  # liste des couples (p:facteur, e: exposant)
        i = 0  # on commence par p = 2
        while i < len(primes) and n > 1:
            p = primes[i]
            if n % p == 0:  # Si p divise n
                j = 0
                while n % p == 0:  # tant que p divise n
                    n //= p  # on divise n par p
                    j += 1  # l'exposant associé augmente de 1
                dec.append((p, j))  # on ajoute le couple à la liste
            i += 1  # on passe au prochain nombre premier
        if n > 1:  # si on a testé tous les facteurs premiers
            dec.append((n, 1))  # cela signifie que n est premier...
        return dec


def affiche_decomposition(n):
    print(' * '.join("{}^{}".format(*ele) for ele in decompose(n)))


affiche_decomposition(13525)
affiche_decomposition(1299709)
affiche_decomposition(541245663)
affiche_decomposition(2147483647)