Décomposition en facteurs premiers
d'un entier de moins de 18 chiffres

Algorithme

Cet algorithme, simple et dépourvu de sophistication, essaie de diviser le nombre donné n par 2, puis par les nombres impairs p = 3, 5, 7, 9, ...

Il y a des essais inutiles, comme tenter de diviser n par 9, mais la simplicité de l'algorithme atténue ce défaut. On évite ainsi de créer une liste de nombres premiers dont la gestion présenterait un coût non négligeable.

En faisant appel à des algorithmes plus raffinés, il serait possible de factoriser de plus grands entiers. Cependant, quelle que soit la méthode utilisée, la factorisation de très grands entiers demeure hors de portée, car la durée des calculs est rédhibitoire. Dans l'avenir, l'ordinateur quantique pourra faire sauter ce verrou.

Critère d'arrêt

Lorsqu'on arrive à n = 1, la factorisation est terminée, mais on peut appliquer un critère d'arrêt qui raccourcit drastiquement la liste des diviseurs p à essayer.

Montrons que, dans le contexte de l'algorithme, si 1 < n < p*p, alors n est un nombre premier. En effet,

• Montrons d'abord que, si n est divisible par p, alors n = p ou n ≥ p*p.
  • Notons d le quotient obtenu: n = p*d. Vu que n a été préalablement divisé par les nombres premiers inférieurs à p, le quotient d n'a pas de diviseur premier inférieur à p. Par suite, d = 1 ou d ≥ p. Ainsi, n = p ou n ≥ p*p.
• Par contraposition, si n ≠ p et n < p*p, alors n n'est pas divisible par p.
• De plus, n n'a pas de diviseur premier plus petit que p. Dans le cas où n = p, il reste vrai que n est un nombre premier puisque n n'a pas de diviseur premier inférieur à n.
• Finalement, si 1 < n < p*p, alors n est un nombre premier.
  • Cette règle ne s'applique pas seulement à la valeur initiale de n, mais à la suite des valeurs décroissantes de n produites par les divisions successives. Partons par exemple de l'état {n=14, p=2}; son traitement retient le facteur 2 et passe à l'état {n=7, p=3}; vu que 7 < 3*3, on peut affirmer que 7 est un nombre premier, qu'il est le dernier diviseur de 14, après quoi on peut arrêter les calculs.
  • Dans l'algorithme, cette règle est mise en oeuvre sous la forme: si n < p*p, alors la valeur suivante attribuée à p est p = n. Il s'agit du dernier facteur premier de la décomposition puisque, à l'étape suivante, n prendra la valeur 1, ce qui achèvera la factorisation.
  • La décroissance de la suite des n et la croissance de la suite des p contribuent toutes deux à la survenue rapide de l'événement conclusif n < p*p.

En langage PHP

Input: $n via un formulaire HTML.

$out1 = "<h3>".$n." = "; $out2 = ""; $n0 = $n; $suivant = false; $p = 2; $e = 0; while ($n % $p == 0) { $n = $n / $p; $e++; } if ($e >= 1) { if ($suivant) { $out1 .= ' × '; } else { $suivant = true; } $out1 .= $p; if ($e > 1) { $out1 .= '^{' .$e.'}'; } elseif ($p==$n0){ $out2 .= '<h3>'.$n0 ." est premier</h3>"; } } $p = 3; while ($n > 1) { $e = 0; while ($n % $p == 0) { $n = $n / $p; $e++; } if ($e >= 1) { if ($suivant) { $out1 .= ' × '; } else { $suivant = true; } $out1 .= $p; if ($e > 1) { $out1 .= '^{' .$e.'}'; } elseif ($p==$n0){ $out2 .= '<h3>'.$n0 ." est premier</h3>"; } } if($n < $p*$p) { $p = $n; } else { ++$p; ++$p; } } $out1 .= '</h3>'; if (strlen($out2)==0){ echo $out1; } else { echo $out2; }