Calculateur de décomposition en facteurs premiers

Décomposer un nombre en nombres premiers

Tout entier supérieur à 1 peut s'écrire comme un produit de nombres premiers d'une seule façon, à l'ordre des facteurs près. C'est le théorème fondamental de l'arithmétique, et la décomposition en facteurs premiers d'un nombre est ce produit unique. Par exemple, 360 = 2³ × 3² × 5. Ce calculateur trouve la décomposition de tout nombre entier jusqu'à 9,007,199,254,740,991, soit 2^53 − 1, le plus grand entier qu'un navigateur peut représenter exactement. Les résultats s'affichent sous forme exponentielle, sous forme entièrement développée et sous forme d'arbre de facteurs.

Les diviseurs, leur nombre et leur somme

Une fois la décomposition en facteurs premiers connue, de nombreuses autres propriétés en découlent directement. Si un nombre est égal à p₁^a₁ × p₂^a₂ × …, le nombre de ses diviseurs positifs est (a₁ + 1)(a₂ + 1)…, car chaque diviseur choisit pour chaque nombre premier un exposant compris entre 0 et la puissance complète. La somme des diviseurs est le produit des (1 + p + p² + … + p^a) sur l'ensemble des nombres premiers. Pour 360, on obtient 4 × 3 × 2 = 24 diviseurs dont la somme vaut 1170. L'outil liste tous les diviseurs par ordre croissant, ce qui aide à trouver des facteurs communs, à simplifier des fractions et à vérifier si un nombre est parfait, c'est-à-dire si la somme de ses diviseurs autres que lui-même est égale au nombre.

Comment fonctionne la décomposition

Les petits facteurs premiers sont éliminés par divisions successives à l'aide d'une roue qui saute les multiples de 2 et de 3. Ce qui reste ne possède que de grands facteurs premiers : le calculateur le vérifie donc avec un test de Miller-Rabin déterministe et, s'il est composé, le scinde avec l'algorithme rho de Pollard (Pollard's rho) en arithmétique BigInt exacte, puis le décompose récursivement. Ainsi, même les produits de deux nombres premiers de l'ordre de plusieurs dizaines de millions sont traités rapidement, là où de simples divisions successives seraient lentes. L'arbre de facteurs montre une façon d'atteindre les nombres premiers en retirant à chaque étape le plus petit nombre premier.

Le mode par lot vous permet de coller toute une liste de nombres et d'obtenir un tableau avec la décomposition et le nombre de diviseurs de chacun, tandis que les saisies invalides sont signalées individuellement sans interrompre le traitement. Tout est calculé dans votre navigateur : les nombres que vous saisissez ne sont jamais envoyés.