Les factorisations d’un entier naturel

1. Décomposition en facteurs premiers

Soit n un entier naturel quelconque. Pour le décomposer en un Produit de facteurs premiersproduit de facteurs premiers, on commence par essayer de le diviser autant de fois qu’il est possible par 2. Chaque fois qu’une division est possible, on affiche 2 et on remplace n par le quotient euclidien n//2. Une fois toutes les divisions par 2 « épuisées », on passe aux divisions par 3, puis par 4, puis par 5, puis par 6 et ainsi de suite. Comme toutes ces divisions successives sont « épuisées » au fur et à mesure de l’avancée du programme, les nouvelles valeurs de n ne sont pas divisibles par les multiples de 2, de 3, de 4, de 5, etc. Finalement, seules les divisions possibles et répétées par les nombres premiers de l’intervalle [1;n] sont prises en compte. On utilise en quelque sorte une variante moderne du crible d’Ératosthène qui rayait successivement dans un tableau de nombres les multiples de 2, de 3, de 5, etc. À la fin, il ne reste plus que les nombres premiers. Le programme est le suivant :...