Devoir pratique n°12 : diviseurs communs et nombres premiers avec k

Exercice 1 : les diviseurs communs (8 pts)

On saisit deux entiers a et b strictement positifs (saisies contrôlées) et on veut compter leurs diviseurs communs : 12 et 18 ont 4 diviseurs communs, 1, 2, 3 et 6.

• 1) Créer un programme Python et l'enregistrer sous le nom DivCommuns.py (1 pt).
• 2) Écrire la fonction NbDivCommuns(a, b) qui renvoie le nombre de diviseurs communs de a et b (4 pts).
• 3) Écrire le programme principal en Python qui lit a et b puis affiche le résultat sous la forme de l'exemple (3 pts).

Exemple : pour a = 12 et b = 18, le programme affiche :

12 et 18 ont 4 diviseurs communs

Exercice 2 : les nombres premiers avec k (12 pts)

Deux entiers sont premiers entre eux quand leur seul diviseur commun est 1, c'est-à-dire quand la fonction NbDivCommuns de l'exercice 1 (recopiée dans ce programme) renvoie 1. On veut lire un tableau T de n entiers strictement positifs (2 ≤ n ≤ 30, saisies contrôlées), puis un entier k strictement positif (saisie contrôlée), trier T du plus grand au plus petit par le tri par sélection, et afficher les éléments de T premiers avec k.

• 1) Créer un programme Python et l'enregistrer sous le nom PremiersAvec.py (1 pt).
• 2) Écrire la procédure Remplir(T, n) qui lit les n éléments de T, chacun strictement positif (2 pts).
• 3) Écrire la procédure TriSelection(T, n) qui trie T dans l'ordre décroissant (4 pts).
• 4) Écrire la procédure PremiersAvec(T, n, k) qui affiche sur une ligne, séparés par un espace, les éléments de T premiers avec k, en appelant NbDivCommuns (3 pts).
• 5) Écrire le programme principal en Python qui lit n, T et k, trie T, puis affiche « Premiers avec k : » suivi des éléments trouvés (2 pts).

Exemple : pour n = 5, T = 35, 9, 25, 49, 8 et k = 6, le programme affiche :

Premiers avec 6 : 49 35 25