Type de calculatrice
TI
Prérequis
L’algorithme d’Euclide repose sur le principe de la division euclidienne : soient deux entiers , et le reste de la division euclidienne de par , alors le PGCD de et est le même que le PGCD de et . Ainsi, par divisions euclidiennes successives on arrive à déterminer le PGCD de deux entiers.
Description
Programme
Le programme prend deux entiers et effectue la division de par , de reste , ensuite prend la valeur de , et prend la valeur de , la boucle est répétée tant que . Alors la valeur de est le PGCD recherché.
Variables
et deux entiers entrés par l’utilisateur tels que
un entier calculé par le programme
Algorithme
|demander et
| le reste de la division euclidienne de par
|tant que
| prend la valeur de
| prend la valeur de
| le reste de la division euclidienne de par
|afficher
Programme TI
↵
|
« Prompt » « A »
« Prompt » « B »
« NUM » « ent( »
« A » « B »
« B » « ➔ » « R »
« ≠ »
« R » « ➔ » « B »
« NUM » « ent( »
« A » « B »
« B » « ➔ » « R »
« End »
« Disp » « B »
Remarque
Décortiquons l’instruction sur un exemple.
Prenons et alors :
- donc
- donc
- ainsi , c’est le reste () de la division euclidienne de par .
Cours associés
Arithmétique et problèmes de codage