# Fonctions et variables globales ---------------------------------------------
def nombrePremiers(a):
    lst=[2,3]
    x = lst[len(lst)-1]
    i=1#on commence a partir de 3
    while lst[i]<=a:#tant que le dernier nombre de la liste est inferieur ou egal au nombre demandé
        x+=2#futur candidat à être un nombre impair
        k=1
        while x%lst[k]!=0:#on teste si le candidat est divisible par les nombre premiers precedent
            k+=1#pour passer au nombre premier suivant
            if k==len(lst) or lst[k]**2>x:#si k à fait toute la liste ou que un elem de la liste **2 est superieur au candidat
                lst.append(x)#on ajoute le candidat à la liste
                i+=1#on se place sur ce nombre pour la suite
                break
    return lst

 #Fonction prenant en argument un entier x à réduire selon p entier premier
 #Retourne x le reste de la division successive par p ainsi que e l'exposant
def expoFacteur(x,p):
    e=0
    while x%p==0:
        x//=p
        e+=1
    return x,e

def decompose():
    liste,fac,exp=[],[],[]
    while True:#demande des nombres a ajouter a la liste
        entree= input("Entier ou stop")
        if entree=="stop":
            break
        liste.append(int(entree))#on ajoute les nombres à la liste
    prems=[2,3]
    for x in liste:#prend les valeurs de la liste position par position
        r=x
        p=2
        facx=[]
        expx=[]
        i=0
        while r!=1:#tant que le nombre de la liste n'est pas egale a 1
            r,e=expoFacteur(r,p)#cf au dessus
            if e!=0:#si l'exposant != 0
                facx.append(p)
                expx.append(e)
            i+=1
            if i==len(prems):
                prems=premierSuivant(prems)
            p = prems[i]
            if r==x and p**2>x:
                break
        fac.append(facx)
        exp.append(expx)
        print(x," = ",end='')
        formateDecomp(facx,expx)
    print("Nombres premiers utilisé",prems)

 #Formate et affiche la décomposition d'un nombre en facteurs premiers
 #fac : tableau contenant les facteurs du nombre à décomposer
 #exp : exposant des facteurs du nombre a décomposer
def formateDecomp(fac,exp):
    if fac==[]:#si il n'y a pas de nombre dans la liste le nombre est premier
        print("est premier")
    else:
        for i in range(len(fac)-1):#genere l'affichage jusqu'à l'avant dernier facteur
            print(fac[i],'^',exp[i],'*',end=' ')
        print(fac[len(fac)-1],'^',exp[len(fac)-1])#rajoute la partie manquante de l'affichage(sous idle '\b' indispo)

 #Fonction prenant en argument un tableau contenant les n premiers entiers premiers
 #Retourne un tableau contenant les n+1 premiers entiers premiers
def premierSuivant(prems):
    x = prems[len(prems)-1] # point de départ : le dernier premier connu
    while True:
        x+=2 # On test les entiers impairs uniquement
        k=1
        while x%prems[k]!=0: # tant que le candidat x n'est pas divisible par un nombre premier il peux encore etre premier
            k+=1
            #si on a testé tout les nombres premiers ou que les nombres premiers restant
            # ne peuvent pas etre le plus petit divisuer du candidat alors x est premier
            if k==len(prems) or prems[k]**2>x:
                prems.append(x)
                return prems

if __name__ == '__main__':
    decompose()