Masar
Masar
Bac Tunisie
Informatique/RA-D
Entraîner la reconnaissance
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'à n\sqrt{n}, ou décomposition en facteurs premiers. La traduction du raisonnement mathématique en boucles est le point central.

Signature de reconnaissance — l'énoncé se trahit ainsi

« É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 »

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué
  1. É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).
  2. Écrire une fonction `EstPremier(n)` qui retourne `VRAI` si nn est premier.
    1. Pourquoi suffit-il de tester les diviseurs jusqu'à ⌊n⌋\lfloor \sqrt{n} \rfloor ?
    2. Tester si 97 est premier. Combien de divisions sont nécessaires ?
  3. Écrire une procédure `Decomposer(n)` qui affiche la décomposition de nn en facteurs premiers. Appliquer à n=360n = 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
```

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 = 23×32×52^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).
```python
def pgcd(a, b):
while b != 0:
a, b = b, a % b
return a
print(pgcd(252, 84))
```

Méthode / Automatismes
  • PGCD itératif (Euclide) : `TantQue b≠0 : r←a mod b ; a←b ; b←r`. Résultat : a.
  • Primalité : tester les diviseurs de 2 à ⌊n⌋\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.
  • PPCM(a,b)=a×bPGCD(a,b)\text{PPCM}(a,b) = \dfrac{a \times b}{\text{PGCD}(a,b)} — souvent demandé en même temps que PGCD.
Pièges classiques

Pièges fréquents : oublier le cas n<2 dans le test de primalité ; s'arrêter à n−1\sqrt{n}-1 au lieu de ⌊n⌋\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).

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