Devoir pratique n°11 : décomposition en facteurs premiers et décompositions triées

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

Tout entier n ≥ 2 s'écrit comme un produit de nombres premiers rangés dans l'ordre croissant : 60 = 2*2*3*5. L'entier saisi doit être au moins égal à 2 (saisie contrôlée).

• 1) Créer un programme Python et l'enregistrer sous le nom Facteurs.py (1 pt).
• 2) Écrire la procédure Decomposer(n) qui affiche la décomposition de n sous la forme de l'exemple (4 pts).
• 3) Écrire le programme principal en Python qui lit n puis appelle Decomposer (3 pts).

Exemple : pour n = 60, le programme affiche :

60 = 2*2*3*5

Exercice 2 : les décompositions dans l'ordre décroissant (12 pts)

On veut lire un tableau T de n entiers (2 ≤ n ≤ 30, saisie contrôlée), chacun au moins égal à 2 (saisie contrôlée), le trier du plus grand au plus petit par la méthode du tri par sélection, puis afficher la décomposition en facteurs premiers de chaque élément, dans cet ordre, avec la procédure Decomposer de l'exercice 1, recopiée dans ce programme.

• 1) Créer un programme Python et l'enregistrer sous le nom Decompositions.py (1 pt).
• 2) Écrire la procédure Remplir(T, n) qui lit les n éléments de T, chacun au moins égal à 2 (3 pts).
• 3) Écrire la procédure TriSelection(T, n) qui trie T dans l'ordre décroissant : pour chaque position i, on cherche le plus grand élément entre i et n - 1 et on l'échange avec T[i] (4 pts).
• 4) Écrire le programme principal en Python qui lit n (saisie contrôlée), remplit et trie T, puis appelle la procédure Decomposer pour chaque élément de T (4 pts).

Exemple : pour n = 3 et les valeurs 60, 12, 97, le programme affiche :

97 = 97
60 = 2*2*3*5
12 = 2*2*3