Factorisation en nombres premiers

Un article de Wikipedia.

Sommaire

Factorisation en nombres premiers

But

Factoriser un entier en produits de nombres premiers.

Introduction

  • Un nombre premier est un nombre entier divisible uniquement par 1 et par lui-même comme pour 2,3,37 et 1039.
  • Tout nombre entier peut être factorisé de manière unique sous la forme de produits de nombres premiers.
  • Algorithme

La méthode utilisée consiste à tenter de diviser l'entier à factoriser n par les nombres premiers p inférieurs à √n.

Si un nombre premier p divise n. La procédure est répétée sur k=n/p en recherchant les nombres premiers p' qui divise k pour √(k)>=p'>=p.

Résultat

Conclusions

Ressources