Le PGCD (plus grand commun diviseur) de deux nombres entiers, différents de 0, est le plus grand nombre entier qui les divise tous les deux. Par exemple, le PGCD de 1028 et de 160 est 32, puisque leurs diviseurs communs sont 1, 2, 4, 9, 16 et 32. La notion de PGDC permet de simplifier les calculs de factions (a/b) en divisant a et b par leur PGCD.

La fonction math.gcd ( ), de la bibliothèque standard de Python, retourne le PGCD des 2 int ( ) passés en arguments, mais cette facilité n'est pas disponible avec tous les langages de programmation. Pourrez-vous trouver un algorithme qui sera capable de suppléer à cette absence ?

Il existe plusieurs méthodes pour calculer le PGCD de 2 nombres entiers a et b, dans cette présentation, nous utiliserons la méthode dite des divisions euclidiennes successives. Cette méthode consiste à : 

- effectuer une division entière avec les deux nombres entiers (a et b) ; 

- si le reste est égal à 0, la valeur du plus petit nombre est le PGCD ;

- sinon garder la valeur du plus petit nombre (soit a soit b) et de le diviser par le reste obtenu précédenment ;

- on recommence tant que le reste est différent de 0.

Par exemple avec les nombres entiers 782 et 221 on obtient :

782 ÷ 221 = 1 avec un reste de 102,

on remplace donc 782 par 221 et 221 par 102 et on recommence.

221 ÷ 102 = 1 avec un reste de 17,

102 ÷ 17 = 6 avec un reste de 0

donc 17 est le PGCD de 782 et 221.

Le programme doit :

1. demander à l'utilisateur de saisir 2 nombres entiers ;

2. vérifier la validités des saisies (nombres entiers non nul) ;

3. calculer le PGCD en effectuant les divisions successives ;

4. afficher les 2 nombres saisies et leur PGCD ;

5. recommencer ou sortir du programme selon le choix de l'utilisateur.

D'abord, faite-le fonctionner. Ensuite, faite-le beau. Enfin, faite-le performant.

Amusez-vous bien !

Télécharger RETROGICIEL - PGCD par divitions.

Cette présentation nécessite que Python 3 soit installé sur votre machine.

Après avoir téléchargé le fichier Pgcd par divisions.7z, décompressez-le dans le répertoire de votre choix.

Ouvrez le répertoire qui vient d'être créé.

Lancez le fichier Retrogiciel.py.

Cliquez sur l'onglet RUN et testez le programme.

Créez votre propre script dans un des langages proposés ou un autre de votre choix.

Le répertoire contient aussi : 

- Python.py, l'exemple en PYTHON sans tkinter ;

- Tkinter.py, l'exemple en PYTHON avec tkinter ;

- Qb84.bas, l'exemple en QBASIC avec qb64 ;

- Bbc.bas, l'exemple en BBC BASIC avec bbc sdl.

# --- Origine Nerd ---

# --- RETROGICIEL - PYTHON ---

# --- PGCD par divisions ---

# -*- coding: utf-8 -*-

# --- PRESENTATION ---

print ( "CALCULER LE PGCD DE DEUX NOMBRES ENTIERS" )

print ( "PAR LA METHODE DES DIVISIONS SUCCESSIVES." )

# --- BOUCLE PRINCIPALE ---

while True :

# --- Saisies et controles des 2 nombres entiers ---

kpremier = input ( "\nEntrez le premier nombre entier ... " )

ksecond = input ( "Entrez le second nombre entier ... " )

kvalide = True

# --- Controle de la validité des nombres ---

try :

kpremier = int ( kpremier )

ksecond = int ( ksecond )

if ksecond > kpremier : kpremier , ksecond = ksecond , kpremier

kpremier // ksecond # --- teste que les nombres sont différent de 0

except :

print ( "\nERREUR DE SAISIES.\nVeuillez saisir 2 nombres entiers.\n" )

kvalide = False

# --- Recheche et affichage du PGCD ---

if kvalide :

print ( f"Le PGDC de { kpremier } et { ksecond }" , end = " " )

while True :

kreste = kpremier % ksecond

kpremier , ksecond = ksecond , kreste

if kreste == 0 :

print ( f"est : { kpremier }.\n" )

break

# --- Choix du bouclage du programme ---

kchoix = input ( "Voulez-vous calculer un autre PGCD (O ou N) ?" )

if kchoix.upper ( ) == "N" : break

# --- FIN DU PROGRAMME ---

print ( "Au revoir" )

# --- Programme : JFB ---

# --- Mai 2024 ---

# --- Fin ---

Pour mieux comprendre l'exemple en PYTHON sans tkinter.

# --- Origine Nerd ---

# --- RETROGICIEL - TKINTER ---

# --- PGCD par divisions ---

# -*- coding: utf-8 -*-

# --- IMPORTATION DES MODULES ---

# --- Modules de la bibliothèque standard ---

import tkinter

# --- DÉFINITION DES FONCTIONS PERSONNALISEES ---

# --- Calcul du PGCD des deux termes saisis ---

def FNC_Calculer ( ) :

# --- Convertion et compatibilité des saisies ---

LAB_Pgcd [ "text" ] = ""

try :

kpremier = int ( ENT_Premier.get ( ) )

ksecond = int ( ENT_Second.get ( ) )

if ksecond > kpremier : kpremier , ksecond = ksecond , kpremier

kpremier // ksecond # --- teste que les nombres sont différent de 0

except :

LAB_Pgcd [ "text" ] = "ERREUR DE SAISIES.\nVeuillez saisir 2 nombres entiers."

return

# --- Recheche du PGCD ---

while True :

kreste = kpremier % ksecond

kpremier , ksecond = ksecond , kreste

if kreste == 0 : break

# --- Affichage du PGCD ---

LAB_Pgcd [ "text" ] = f"Le PGCD de { ENT_Premier.get ( ) } et { ENT_Second.get ( ) }\nest : { kpremier }."    

# --- CREATION DE L'INTERFACE GRAPHIQUE ---

# --- Création de la fenêtre principale ---

TKI_Principal = tkinter.Tk ( )

TKI_Principal.title ( "RETROGICIEL - pgcd par divisions" )

# --- Création des controles nommées ---

ENT_Premier = tkinter.Entry ( TKI_Principal , width = 7 )

ENT_Second = tkinter.Entry ( TKI_Principal , width = 7 )

LAB_Pgcd = tkinter.Label ( TKI_Principal , fg = "blue" , font = ( None , 10 , "bold" ) , height = 3 )

# --- Mise en place des controles (anonymes et nommés) dans la fenêtre principale ---

tkinter.Label ( TKI_Principal , text = "\nCalcul du PGCD\n2 NOMBRES\n" ).grid ( row = 0 , column = 0 , columnspan = 2 , sticky = "nesw" )

tkinter.Label ( TKI_Principal , text = "Premier nombre :" , justify = "right" ).grid ( row = 1 , column = 0 , sticky = "e" )

ENT_Premier.grid ( row = 1 , column = 1 , sticky = "w" )

tkinter.Label ( TKI_Principal , text = "Second nombre :" , justify = "right" ).grid ( row = 2 , column = 0 , sticky = "e" )

ENT_Second.grid ( row = 2 , column = 1 , sticky = "w" )

tkinter.Button ( TKI_Principal , text = "Calculer ..." , command = FNC_Calculer ).grid ( row = 3 , column = 0 , columnspan = 2 , sticky = "nesw" )

LAB_Pgcd.grid ( row = 4 , column = 0 , columnspan = 2 , sticky = "nesw" )

tkinter.Button ( TKI_Principal , text = "Quitter" , command = TKI_Principal.destroy ).grid ( row = 5 , column = 0 , columnspan = 2 , sticky = "nesw" )

# --- DEBUT DU PROGRAMME ---

TKI_Principal.mainloop ( )

# --- Programme : JFB ---

# --- Mars 2023 ---

# --- Fin ---

Pour mieux comprendre l'exemple en PYTHON avec tkinter.

' --- Origine Nerd propose pour ---

' --- RETROGICIEL - QB64 ---

' --- PGCD par divisions ---

' --- DEBUT DU PROGRAMME ---

PRINT "CALCULER LE PGCD DE DEUX NOMBRES ENTIERS"

PRINT "PAR LA METHODE DES DIVISIONS SUCCESSIVES."

' --- BOUCLE PRINCIPALE ---

DO

' --- Saisie des deux nombres entiers ---

INPUT "Entrez le premier nombre entier ", kpremier&

INPUT "Entrez le second nombre entier ", ksecond&

IF kpremier& < ksecond& THEN SWAP kpremier&, ksecond&

PRINT "Le PGCD de "; kpremier&; " et "; ksecond&; " est ";

' --- Calcul du pgcd ---

DO

kreste& = kpremier& MOD ksecond&

kpremier& = ksecond&

ksecond& = kreste&

LOOP UNTIL kreste& = 0

' --- Affichage du pgdc, s'il existe, des deux nombres saisis ---

PRINT kpremier&

' --- Bouclage du prgramme ---

PRINT

INPUT "Voulez-vous recommencer [ O ou N ] "; kchoix$

LOOP UNTIL UCASE$(kchoix$) = "N"

' --- FIN DU PROGRAMME ---

PRINT "Au revoir."

END

' --- Programme : JFB ---

' --- Mai 2024 ---

' --- Fin ---

Pour mieux comprendre l'exemple en QB64.

REM --- Origine Nerd propose pour ---

REM --- RETROGICIEL - BBC BASIC ---

REM --- PGCD par divisions ---

REM --- DEBUT DU PROGRAMME ---

PRINT "CALCULER LE PGCD DE DEUX NOMBRES ENTIERS"

PRINT "PAR LA METHODE DES DIVISIONS SUCCESSIVES."

REM --- BOUCLE PRINCIPALE ---

REPEAT

REM --- Saisie des deux nombres par l'utilisateur ---

INPUT "Entrez le premier nombre entier ", kpremier

INPUT "Entrez le second nombre entier ", ksecond

IF kpremier < ksecond THEN SWAP kpremier, ksecond

PRINT "Le PGCD de "; kpremier; " et "; ksecond; " est ";

REM --- Calcul du pgcd ---

REPEAT

kreste = kpremier MOD ksecond

kpremier = ksecond

ksecond = kreste

UNTIL kreste = 0

REM --- Affichage du pgcd ---

PRINT STR$(kpremier)

REM --- Bouclage du programme ---

PRINT

INPUT "Voulez-vous recommencer [ O ou N ] "; kchoix$

UNTIL kchoix$ = "N" OR kchoix$ = "n"

REM --- FIN DU PROGRAMME ---

PRINT "Au revoir."

END

REM --- Programme : JFB ---

REM --- Mai 2024 ---

REM --- Fin ---

Pour mieux comprendre l'exemple en BBC BASIC.