Devoir pratique n°3 : décomposition en facteurs premiers et tri des nombres décomposés

Exercice 1 : la décomposition en facteurs premiers (8 pts)

Tout entier n ≥ 2 s'écrit comme un produit de nombres premiers : 60 = 2*2*3*5. On veut afficher cette décomposition pour un entier n de 2 à 100000.

• 1) Créer un programme Python et l'enregistrer sous le nom Decomposition.py (1 pt).
• 2) Écrire la fonction Decomposition(n) qui renvoie la décomposition de n sous forme d'une chaîne, les facteurs dans l'ordre croissant séparés par * (4 pts).
• 3) Écrire le programme principal en Python qui lit n (saisie contrôlée) puis affiche la décomposition sous la forme de l'exemple (3 pts).

Exemple : pour n = 60, le programme affiche :

60 = 2*2*3*5

Exercice 2 : trier des nombres et les décomposer (12 pts)

On veut lire un tableau T de n entiers (2 ≤ n ≤ 20), chacun de 2 à 100000, le trier dans l'ordre croissant par la méthode du tri à bulles, puis afficher la décomposition en facteurs premiers de chaque élément, calculée avec la fonction Decomposition de l'exercice 1.

On recopie dans ce programme la fonction Decomposition de l'exercice 1.

• 1) Créer un programme Python et l'enregistrer sous le nom TriFacteurs.py (1 pt).
• 2) Écrire la procédure Remplir(T, n) qui lit les n éléments de T, chacun de 2 à 100000 (saisie contrôlée) (2 pts).
• 3) Écrire la procédure TriBulles(T, n) qui trie T dans l'ordre croissant : on parcourt le tableau en échangeant deux voisins mal placés, et on recommence tant qu'il y a eu un échange (5 pts).
• 4) Écrire la procédure AfficherDecompositions(T, n) qui affiche, une ligne par élément, l'élément et sa décomposition sous la forme de l'exemple, en appelant Decomposition (2 pts).
• 5) Écrire le programme principal en Python qui lit n (saisie contrôlée) puis remplit, trie et affiche le tableau (2 pts).

Exemple : pour n = 3 et les valeurs 60, 7, 18, le programme affiche :

7 = 7
18 = 2*3*3
60 = 2*2*3*5