Donc voilà les programmes comme promis:

from math import log, gcd import time def factor(N, debut, f): L = [] while not N&1: N >>= 1 L.append(2) if isprime(N):return (L+[N]) elif N == 1:return L x, y = f(N, debut) if y == 0:return L+[N] if x != 1: if y != 1:L += factor(x, debut, f)+factor(y, debut, f) else:L.append(x) else:L.append(y) return sorted(L) def rho_pollard(n, debut, seed=2): if not isprime(n): x = gcd(pow(2, n, n)-2, n) if 1 != x != n:return x, n//x c = 1 g = n while g==n: y = x = seed cpt, g = 0, 1 while (g==1): x, y = (x*x+c)%n, ((y*y+c)**2+c)%n g = gcd(x-y,n) cpt += 1 if not testemps(time.time(), debut):return "Désoler, le nombre est trop grand...", 0 if n%seed == 0:return seed, n//seed seed += 1 return g, n//g else: return(1, n) def facto(N, debut, f=rho_pollard): Lfac = factor(N, debut, f) dicfac = {} for facteur in Lfac: try: dicfac[facteur] += 1 except: dicfac[facteur] = 1 return dicfac def miller(n, Ld): r, d = 0, n-1 while not d & 1: d >>= 1 r += 1 LL = [] for a in Ld: x = pow(a, d, n) LL.append([]) if x == 1 or x == n-1: continue for i in range(r): y = pow(x, 2, n) if y == 1: return gcd(x-1, n) x = y if x == n - 1: break LL[-1].append(x) else: return False return True def isprime(n): if not n&1:return n == 2 elif n < 9:return n > 2 elif n < 341531:return miller(n, [9345883071009581737]) elif n < 885594169:return miller(n, [725270293939359937, 3569819667048198375]) elif n < 350269456337:return miller(n, [4230279247111683200, 14694767155120705706, 16641139526367750375]) elif n < 55245642489451:return miller(n, [2, 141889084524735, 1199124725622454117, 11096072698276303650]) elif n < 7999252175582851:return miller(n, [2, 4130806001517, 149795463772692060, 186635894390467037, 3967304179347715805]) elif n < 585226005592931977:return miller(n, [2, 123635709730000, 9233062284813009, 43835965440333360, 761179012939631437, 1263739024124850375]) elif n < 18446744073709551616:return miller(n, [2, 325, 9375, 28178, 450775, 9780504, 1795265022]) elif n < 318665857834031151167461:return miller(n, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]) elif n < 3317044064679887385961981:return miller(n, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]) else:return miller(n, range(3, min(n-2, int(log(n)**2)<<1), 2)) def presente(N, debut): L = [] if isprime(N):return f'{N} est premier !' elif N < 4:return f"{N} n'est pas premier, il est une exception" dic = facto(N, debut) Lfac = [] for n, e in dic.items(): Lfac.append(n) if e != 1: L.append(f'{n}^{e}') else: L.append(str(n)) if L == [str(N)]:return f"Le programme n'a pas eu le temps pour factoriser {n}" ecrire(Lfac) return f"la factorisation de {N} est {' * '.join(L)}" def testemps(temps, debut):return False if temps-debut > 170 else True def main(n, _0or_1): if _0or_1: print(presente(n, time.time())) else: p = isprime(n) if p == True:print(f'{n} est premier') elif p != False:print(f"{n} n'est pas premier, il est au moins divisible par {p}") else:print(f"{n} n'et pas premier") if __name__=='__main__': n = int(input('Entrez 0 si vous voulez vérifier la primalité d'un nombre ou 1 si vous voulez le factoriser : ')) N = int(input('Entrez un nombre pour lui exécuté l'opération choisi : ')) main(N, n)