RA-DAlgorithmes récurrents et arithmétiques

Algorithmes arithmétiques — Euclide, primalité, décomposition en facteurs premiers

Idée directrice

L'énoncé donne un ou deux entiers et demande d'implémenter des algorithmes classiques : calcul du PGCD par l'algorithme d'Euclide, test de primalité par essais de division jusqu'à $\sqrt{n}$ , ou décomposition en facteurs premiers. La traduction du raisonnement mathématique en boucles est le point central.

Ce qui aide à reconnaître la démarche

« Écrire l'algorithme du PGCD par la méthode d'Euclide » ; « Donner la trace de l'algorithme d'Euclide pour … » ; « Écrire une fonction qui teste si un entier est premier » ; « Écrire un algorithme de décomposition en facteurs premiers »

Besoin d’un point de départ ? Voir la méthode

PGCD itératif (Euclide) : TantQue b≠0 : r←a mod b ; a←b ; b←r. Résultat : a.
Primalité : tester les diviseurs de 2 à $\lfloor\sqrt{n}\rfloor$ . Cas particuliers : n<2 → non premier.
Décomposition : boucle sur d à partir de 2, diviser n tant que divisible, puis incrémenter d.
Si n>1 en fin de boucle : n est lui-même un facteur premier.
$\text{PPCM}(a,b) = \dfrac{a \times b}{\text{PGCD}(a,b)}$ — souvent demandé en même temps que PGCD.

Les pièges à vérifier dans ta démarche

Pièges fréquents : oublier le cas n<2 dans le test de primalité ; s'arrêter à $\sqrt{n}-1$ au lieu de $\lfloor\sqrt{n}\rfloor$ ; dans la décomposition, oublier d'afficher n si n>1 en fin de boucle (n est alors un facteur premier).

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué

Écrire l'algorithme itératif de l'algorithme d'Euclide pour calculer PGCD(a, b). Appliquer à PGCD(252, 84) en donnant la trace (tableau des valeurs de a et b).
Écrire une fonction EstPremier(n) qui retourne VRAI si $n$ est premier.
1. Pourquoi suffit-il de tester les diviseurs jusqu'à $\lfloor \sqrt{n} \rfloor$ ?
2. Tester si 97 est premier. Combien de divisions sont nécessaires ?
Écrire une procédure Decomposer(n) qui affiche la décomposition de $n$ en facteurs premiers. Appliquer à $n = 360$ .

Voir la correction commentéeAprès avoir posé votre démarche

1. PGCD itératif (Euclide). Tant que b≠0, remplacer (a,b) par (b, a mod b).

TDOL : r entier (reste). Type/Nature : a, b entiers.

DEF FN PGCD(a, b : entier) : entier
Variables r : entier
Début
  TantQue b ≠ 0 faire
    r ← a mod b ; a ← b ; b ← r
  FinTantQue
  Retourner a
Fin

Trace pour PGCD(252, 84) : (252, 84) → (84, 0). On retourne 84.

2. Test de primalité. Un entier n ≥ 2 est premier s'il n'a aucun diviseur dans 2..⌊√n⌋.

DEF FN EstPremier(n : entier) : booléen
Variables i : entier
Début
  Si n < 2 alors Retourner Faux FinSi
  Pour i de 2 à Tronc(Racine(n)) faire
    Si n mod i = 0 alors Retourner Faux FinSi
  FinPour
  Retourner Vrai
Fin

2.(a) Pourquoi s'arrêter à ⌊√n⌋. Si n = d × q avec d ≤ q, alors d² ≤ d × q = n, donc d ≤ √n : tout entier composé possède un diviseur au plus égal à sa racine carrée. Ne trouver aucun diviseur jusqu'à ⌊√n⌋ suffit donc à conclure.
2.(b) Test de 97. ⌊√97⌋ = 9 : on effectue les divisions par 2, 3, 4, 5, 6, 7, 8, 9, soit 8 divisions, aucune n'a un reste nul → 97 est premier. (Sans la borne, il en faudrait 95.)
3. Décomposition en facteurs premiers — appliquer à n = 360.

DEF PROC Decomposer(n : entier)
Variables d : entier
Début
  d ← 2
  TantQue d * d ≤ n faire
    TantQue n mod d = 0 faire
      Écrire(d) ; n ← n div d
    FinTantQue
    d ← d + 1
  FinTantQue
  Si n > 1 alors Écrire(n) FinSi
Fin

360 = 2 × 2 × 2 × 3 × 3 × 5 = $2^3 \times 3^2 \times 5$ . Contrainte : n dans [2..+∞[ ; ne pas oublier d'afficher n s'il reste > 1 en fin de boucle.

Équivalent Python (extrait).

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
print(pgcd(252, 84))

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

Variantes rencontrées : PGCD de trois entiers ; vérification si deux entiers sont premiers entre eux ( $\pgcd = 1$ ) ; liste de tous les nombres premiers jusqu'à N (crible d'Ératosthène).

Exercices d'entraînement — une nuance à la fois

1 Compter les facteurs premiers avec ou sans répétition

Entraînement 01 / 01

Compter les facteurs premiers avec ou sans répétition

2 questionsCorrigé masquéEn cours de relecture

Pour un entier n ≥ 2, on veut calculer Omega(n), le nombre de facteurs premiers avec répétition, et omega(n), le nombre de facteurs premiers distincts. Exemple : 72 = 2×2×2×3×3, donc Omega(72)=5 et omega(72)=2. Les divisions sont entières ; les variables peuvent contenir les nombres utilisés.

Écrire une procédure Facteurs(n, total, distincts), avec TDOL, qui produit les deux compteurs par divisions successives. Traiter le facteur premier éventuel restant après la boucle.
Donner la trace pour n = 72, puis les résultats pour n = 13 et n = 49. Justifier pourquoi on utilise dd ≤ reste et non dd < reste.

Cet exercice et sa correction sont en cours de relecture. Tu peux les consulter ; l’exercice n’est pas encore proposé en séance.

Voir la correction commentéeAprès avoir posé votre démarche

Contrat et objets. n entier d’entrée, au moins 2 ; total et distincts entiers de sortie (var). TDOL : reste entier (partie restant à factoriser), d entier (diviseur testé), present booléen (au moins une division par ce d).

0) DEF PROC Facteurs(n:entier ; var total,distincts:entier)
1) reste ← n ; d ← 2 ; total ← 0 ; distincts ← 0
2) TantQue d*d ≤ reste faire
     present ← Faux
     TantQue reste mod d = 0 faire
       reste ← reste div d
       total ← total+1
       present ← Vrai
     FinTantQue
     Si present alors distincts ← distincts+1 FinSi
     d ← d+1
   FinTantQue
3) Si reste > 1 alors
     total ← total+1 ; distincts ← distincts+1
   FinSi
4) Fin Facteurs

Trace de 72. Avec d=2, reste parcourt 72→36→18→9 : total=3 et distincts=1. Avec d=3, reste parcourt 9→3→1 : total=5 et distincts=2. Le résidu vaut 1, donc rien n’est ajouté. Pour 13, aucune division ne réussit et le résidu premier 13 ajoute un facteur : (total,distincts)=(1,1). Pour 49, d=7 donne 49→7→1, d’où (2,1).

Pourquoi ces bornes ? Les facteurs plus petits que d ont déjà été retirés. Si reste>1 et dd>reste à la sortie, un résidu composé posséderait un diviseur premier inférieur à d, contradiction : le résidu est premier. À l’égalité dd=reste, il faut encore tester d : l’omettre ferait compter 49 comme un seul facteur. total augmente à chaque division, distincts une seule fois par diviseur rencontré.

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.