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, dans cette présentation, nous utiliserons la méthode dite par décomposition de facteurs premiers. Cette méthode consiste à décomposer les 2 nombres en 2 suites de facteurs premiers.  Pour connaitre leur PGDC, on multiplie tous les facteurs premiers communs aux 2 nombres.

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

126000 = 2 x 2 x 2 x 2 x 3 x 3 x 5 x 5 x 5 x 7

35640 = 2 x 2 x 2 x 3 x 3 x 3 x 3 x 5 x 11

2 x 2 x 2 x 3 x 3 x 5 = 360

360 est le PGCD de 126000 et 35640

Le programme doit :

1. connaître suffisamment nombres de nombres premiers ;

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

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

4. décomposer le premier nombre en facteurs prémiers ;

5. décomposer le second nombre en facteurs prémiers ;

6. multiplier les facteurs premiers communs aux 2 nombres, c'est le PGCD ; 

7. afficher les 2 nombres saisies et leur PGCD ;

8. 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 décomposition .

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

Après avoir téléchargé le fichier Pgcd par decomposition.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 décomposition ---

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

# --- INITIALISATION GENERALE ---

LST_Suites = [ ]

TPL_Premiers = ( 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 ,

107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 )

# --- DÉFINITION DES FONCTIONS POUR PROGRAMME ADAPTE ---

# --- Décomposition d'un nombre en facteurs premiers ---

def FNC_Decomposition ( Q ) :

ksuite = [ ]

if Q < 0 : Q = abs ( Q )

for kpremier in TPL_Premiers :

while True :

if Q % kpremier != 0 : break

ksuite.append ( kpremier )

Q = Q // kpremier

if Q < kpremier : break

if Q not in ( 0 , 1 ) : ksuite.append ( Q )   

return ksuite

# --- DEBUT DU PROGRAMME ---

# --- PRESENTATION ---

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

print ( "PAR LA METHODE DE LA DECOMPOSITON" )

print ( "EN FACTEUR PREMIERS." )

# --- 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 )

except :

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

kvalide = False

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

if kvalide :

# --- Décomposition des nombres saisies ---

LST_Suites.clear ( )

LST_Suites.append ( FNC_Decomposition ( kpremier ) )

LST_Suites.append ( FNC_Decomposition ( ksecond ) )

# --- Analyse des décompositions et calcul du PGCD ---

kpgcd = 1

kfacteurs = set ( LST_Suites [ 0 ] )

for kfacteur in kfacteurs :

knombre = min ( LST_Suites [ 0 ].count ( kfacteur ) , LST_Suites [ 1 ].count ( kfacteur ) )

kpgcd *= kfacteur ** knombre

# --- Affichage du PGCD ---

print ( f"le PGCD de { kpremier } et { ksecond } est : { kpgcd }." )   

# --- 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 décompositions ---

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

# --- IMPORTATION DES MODULES ---

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

import tkinter

# --- INITIALISATION GENERALE ---

LST_Suites = [ ]

TPL_Premiers = ( 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 ,

107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 )

# --- 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 ( ) )

except :

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

return

    # --- Décomposition des nombres saisies ---

    LST_Suites.clear ( )

    LST_Suites.append ( FNC_Decomposition ( kpremier ) )

    LST_Suites.append ( FNC_Decomposition ( ksecond ) )

# --- Analyse des décompositions et calcul du PGCD ---

kpgcd = 1

kfacteurs = set ( LST_Suites [ 0 ] )

for kfacteur in kfacteurs :

knombre = min ( LST_Suites [ 0 ].count ( kfacteur ) , LST_Suites [ 1 ].count ( kfacteur ) )

kpgcd *= kfacteur ** knombre

# --- Affichage du PGCD ---

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

# --- Décomposition d'un nombre en facteurs premiers ---

def FNC_Decomposition ( Q ) :

ksuite = [ ]

if Q < 0 : Q = abs ( Q )

for kpremier in TPL_Premiers :

while True :

if Q % kpremier != 0 : break

ksuite.append ( kpremier )

Q = Q // kpremier

if Q < kpremier : break

if Q not in ( 0 , 1 ): ksuite.append ( Q )   

return ksuite

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

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

TKI_Principal = tkinter.Tk ( )

TKI_Principal.title ( "RETROGICIEL - pgcd par décomposition" )

# --- 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 = "CALCULER LE PGCD DE 2 NOMBRES" ).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 = "Exit" , 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 decomposition ---

' --- INITIALISATION DES VARIABLES GLOBALES ---

DIM SHARED LST_Nombres(2) AS LONG

DIM SHARED LST_Facteurs(2, 100) AS INTEGER

' --- DEBUT DU PROGRAMME ---

PRINT "CALCULER LE PGCD DE DEUX NOMBRES ENTIERS PAR LA METHODE"

PRINT "DITES DE DECOMPOSITION EN FACTEURS PREMIERS."

' --- BOUCLE PRINCIPALE ---

DO

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

INPUT "Entrez le premier nombre entier ", LST_Nombres(1)

INPUT "Entrez le second nombre entier ", LST_Nombres(2)

' --- Decomposition en facteurs premiers ---

kmaximum = FNC_Decomposer

' --- Calcul du pgcd ---

kpgcd = FNC_Pgcd(kmaximum)

' --- Affichage du pgcd ---

PRINT "Le PGDC de"; LST_Nombres(1); "et"; LST_Nombres(2); "est"; kpgcd

' --- Bouclage du programme ---

PRINT

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

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

' --- FIN DU PROGRAMME ---

PRINT "Au revoir."

END

' --- DEFINITION DES FONCTIONS PERSONNALISEES ---

' --- Decomposition des deux nombres en facteurs premiers ---

FUNCTION FNC_Decomposer

ERASE LST_Facteurs

kmaximum = 0

FOR kvaleur = 1 TO 2

kanalyse = LST_Nombres(kvaleur)

IF kanalyse < 0 THEN kanalyse = ABS(kanalyse)

kindex = 0

RESTORE

DO

READ kfacteur

DO

IF kanalyse MOD kfacteur <> 0 THEN EXIT DO

LST_Facteurs(kvaleur, kindex) = kfacteur

kanalyse = INT(kanalyse / kfacteur)

kindex = kindex + 1

IF kfacteur > kmaximum THEN kmaximum = kfacteur

LOOP

IF kanalyse < kfacteur THEN EXIT DO

LOOP WHILE kfacteur <> 199

NEXT

FNC_Decomposer = kmaximum

END FUNCTION

' --- Calcul du pgcd ---

FUNCTION FNC_Pgcd (Q)

kpgcd = 1

RESTORE

DO

READ kfacteur

kquota_a = 0

kquota_b = 0

FOR kindex = 0 TO 100

IF LST_Facteurs(1, kindex) + LST_Facteurs(2, kindex) = 0 THEN EXIT FOR

IF LST_Facteurs(1, kindex) = kfacteur THEN kquota_a = kquota_a + 1

IF LST_Facteurs(2, kindex) = kfacteur THEN kquota_b = kquota_b + 1

NEXT

IF kquota_a < kquota_b THEN kpuissance = kquota_a ELSE kpuissance = kquota_b

kpgcd = kpgcd * (kfacteur ^ kpuissance)

LOOP WHILE kfacteur <> Q

FNC_Pgcd = kpgcd

END FUNCTION

' --- VALEURS DES DONNEES ---

' --- Liste des nombres premiers jusque 200 ---

DATA 2,3,5,7,11,13,17,19,23,29,31,37,41,43

DATA 47,53,59,61,67,71,73,79,83,89,97,101,103

DATA 107,109,113,127,131,137,139,149,151,157,163

DATA 167,173,179,181,191,193,197,199

' --- Programme : JFB ---

' --- Mai 2024 ---

' --- Fin ---

Pour mieux comprendre l'exemple en QB64.

REM --- Origine Nerd propose pour ---

REM --- RETROGICIEL - BBC BASIC ---

REM --- PGCD par decomposition ---

REM --- LISTE DES VLEURS DES DONNEES ---

REM --- Listes de nombres premiers jusque 200 ---

DATA 2,3,5,7,11,13,17,19,23,29,31,37,41,43

DATA 47,53,59,61,67,71,73,79,83,89,97,101,103

DATA 107,109,113,127,131,137,139,149,151,157,163

DATA 167,173,179,181,191,193,197,199

REM --- INITIALISATION GENERALE ---

DIM LST_Facteurs(2, 100)

REM --- DEBUT DU PROGRAMME ---

PRINT "CALCULER LE PGCD DE DEUX NOMBRES ENTIERS PAR LA METHODE"

PRINT "DITES DE DECOMPOSITION EN FACTEURS PREMIERS."

REM --- BOUCLE PRONCIPALE ---

REPEAT

REM --- RaZ des listes des décomposeurs ---

FOR knombre = 0 TO 1

FOR kfacteur = 0 TO 100

IF LST_Facteurs(knombre, kfacteur) = 0 THEN EXIT FOR ELSE LST_Facteurs(knombre, kfacteur) = 0

NEXT kfacteur

NEXT knombre

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

INPUT "Entrez le premier nombre entier ", kpremier

INPUT "Entrez le second nombre entier ", ksecond

REM --- Decomposition des deux nombres en faccteurs premiers ---

kmaximum = 0

FOR kvaleur = 0 TO 1

RESTORE

IF kvaleur = 0 THEN kanalyse = kpremier ELSE kanalyse = ksecond

kindex = 0

REPEAT

READ kfacteur

REPEAT

IF kanalyse MOD kfacteur <> 0 THEN EXIT REPEAT

LST_Facteurs(kvaleur, kindex) = kfacteur

kanalyse = kanalyse DIV kfacteur

kindex = kindex + 1

IF kfacteur > kmaximum THEN kmaximum = kfacteu

UNTIL FALSE

IF kanalyse < kfacteur THEN EXIT REPEAT

UNTIL kfacteur = 199

NEXT kvaleur

REM --- Calcul du pgcd (s'il existe) ---

kpgcd = 1

RESTORE

REPEAT

READ kfacteur

kquota_a = 0

kquota_b = 0

FOR kindex = 0 TO 100

IF LST_Facteurs(0, kindex) + LST_Facteurs(1, kindex) = 0 THEN EXIT FOR

IF LST_Facteurs(0, kindex) = kfacteur THEN kquota_a = kquota_a + 1

IF LST_Facteurs(1, kindex) = kfacteur THEN kquota_b = kquota_b + 1

NEXT

IF kquota_a < kquota_b THEN kpuissance = kquota_a ELSE kpuissance = kquota_b

kpgcd = kpgcd * (kfacteur ^ kpuissance)

UNTIL kfacteur = kmaximum

PRINT "Le PGDC de "; kpremier; " et "; ksecond; " est "; kpgcd; "."

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.