Accueil › Cours › Problèmes types

Les leçons de ce chapitre

1. Diviseurs et nombres premiers
2. Les chiffres d'un nombre
3. PGCD et PPCM

Leçon 8.1 : Diviseurs et nombres premiers

9 min

Un nombre d est un diviseur de n si le reste de la division de n par d est 0, c'est-à-dire si n mod d = 0. Pour trouver tous les diviseurs de n, on teste chaque d de 1 à n avec une boucle Pour.

Nombre premier

Un nombre est premier s'il a exactement deux diviseurs : 1 et lui-même. 7 est premier (1 et 7). 12 ne l'est pas (1, 2, 3, 4, 6, 12). 1 n'est pas premier : il n'a qu'un seul diviseur.

Méthode : compte les diviseurs de n. S'il y en a exactement 2, n est premier.

Astuce : On peut aller plus vite : il suffit de tester les d jusqu'à la racine de n. Mais commence par la méthode simple, elle est toujours acceptée.

En Python

On teste tous les nombres de 1 à n : ceux qui divisent n sont affichés.

n = int(input())
print("Diviseurs de", n, ":")
for d in range(1, n + 1):
    if n % d == 0:
        print(d)

En algorithme

Le même programme en algorithme, avec mod.

Algorithme Diviseurs
Début
  Lire(n)
  Ecrire("Diviseurs de ", n, " :")
  Pour d de 1 à n Faire
    Si n mod d = 0 Alors
      Ecrire(d)
    FinSi
  FinPour
Fin

TDO
Objet | Type/Nature
n, d | Entier

Leçon 8.2 : Les chiffres d'un nombre

8 min

Pour retourner un nombre (1234 → 4321), on construit le miroir chiffre par chiffre. À chaque tour : on décale le miroir d'un rang (miroir * 10), on ajoute le dernier chiffre de n (n mod 10), puis on retire ce chiffre de n (n div 10).

Un palindrome numérique est un nombre égal à son miroir : 1221, 7, 4004.

Attention : La boucle détruit n (il finit à 0). Pour comparer ensuite avec le nombre de départ, garde une copie de n avant la boucle.

En Python

Pour 1234 : miroir vaut 4, puis 43, puis 432, puis 4321.

n = int(input())
miroir = 0
while n > 0:
    miroir = miroir * 10 + n % 10
    n = n // 10
print("Miroir :", miroir)

En algorithme

Même méthode avec mod et div.

Algorithme Miroir
Début
  Lire(n)
  miroir ← 0
  TantQue n > 0 Faire
    miroir ← miroir * 10 + n mod 10
    n ← n div 10
  FinTantQue
  Ecrire("Miroir : ", miroir)
Fin

TDO
Objet | Type/Nature
n, miroir | Entier

Leçon 8.3 : PGCD et PPCM

9 min

Le PGCD de deux nombres a et b est leur plus grand diviseur commun. L'algorithme d'Euclide le calcule sans tester tous les nombres : tant que b n'est pas nul, on remplace (a, b) par (b, reste de a ÷ b). Quand b vaut 0, le PGCD est a.

Exemple : PGCD(48, 18) → (18, 12) → (12, 6) → (6, 0). Le PGCD est 6.

Le PPCM

Le PPCM (plus petit multiple commun) se déduit du PGCD : PPCM = a × b div PGCD. On s'en sert pour simplifier les fractions : on divise le numérateur et le dénominateur par leur PGCD.

En Python

À chaque tour (a, b) devient (b, a mod b). Quand b vaut 0, a contient le PGCD.

a = int(input())
b = int(input())
while b != 0:
    r = a % b
    a = b
    b = r
print("PGCD :", a)

En algorithme

L'algorithme d'Euclide en notation algorithmique.

Algorithme Euclide
Début
  Lire(a)
  Lire(b)
  TantQue b ≠ 0 Faire
    r ← a mod b
    a ← b
    b ← r
  FinTantQue
  Ecrire("PGCD : ", a)
Fin

TDO
Objet | Type/Nature
a, b, r | Entier

S'entraîner gratuitement

Chaque leçon a 3 exercices gratuits avec indices, et 8 missions du jeu pour appliquer ce chapitre avec Hannibot.

← Chapitre précédent : Tant que et Répéter · Chapitre suivant : Les tableaux →

Tous les chapitres · Voir les devoirs corrigés de 2ème TI

Cours écrit pour Mission Carthage d'après le programme officiel. Ton professeur reste la référence.