L'Atelier Monstre

Problème : Trouver la valeur maximale de p telle que x = bp, où b est un entier. Par exemple, 25 = 52 et 64 = 26. L'entrée est x, la sortie est p. La solutino repose sur la décomposition en facteurs premiers du nombre donné, followed par le calcul du PGCD des exposants. Fonction de décomposition en facteurs premiers : int facteurs[100]; int exp ...

Théorie des nombres Algorithme d'Euclide pour le PGCD Soient deux entiers positisf \(m,n\) avec \(m > n\). Le plus grand commun diviseur \(\gcd(m,n)\) satisfait la propriété \(\gcd(m,n) = \gcd(n, m \mod n)\). Cette propriété permet de calculer le PGCD par réduction successive jusqu'à obtenir un reste nul. def pgcd(a, b): while b != 0: ...