PGCD de deux entiers – Bac Pratique 2015 [ Algorithme + Python ]

Algo et Python 07-09-24

62 0

Sujet bac informatique pratique 2015 (Bac scientifique)

La décomposition du PGCD(A,B) en facteurs premiers (avec A≥2 et B≥2) est le produit des facteurs premiers apparaissant à la fois dans la décomposition de A et de B munis de plus petit des exposants trouvés dans la décomposition de A et de B.

N.B : On dit qu’un nombre a admet le nombre b comme facteur premier lorsque b est un nombre premier qui divise a.

Ecrire un programme Python qui permet de saisir deux entiers a et b (10≤a≤b), de chercher la décomposition en facteurs premiers du PGCD(A,B) en utilisant le principe ci-dessus.

Exemple : Pour A=378 et B=8820

Liste des facteurs premiers de A=378=2*3³*7.

Liste des facteurs premiers de B=8820=2²*3²*5*7².

Alors le programme affiche : PGCD(378, 8820)= 2*3³*7=126

Solution Algorithmique

1. Saisie des deux entiers et

L'algorithme commence par demander à l'utilisateur de saisir deux entiers et , tels que .

2. Décomposition en facteurs premiers

a) Pour chaque entier et , on effectue une décomposition en facteurs premiers.

b) Cela implique de diviser successivement et par les nombres premiers croissants (commençant par 2) jusqu'à obtenir 1.

c) Pour chaque nombre qui divise ou sans reste, on l'enregistre comme un facteur premier et on continue avec le quotient obtenu.

d) Chaque facteur est enregistré avec son exposant, c'est-à-dire le nombre de fois qu'il divise le nombre en question.

3. Trouver les facteurs communs avec le plus petit exposant

a) L'algorithme identifie les facteurs premiers communs aux deux nombres et .

b) Pour chaque facteur commun, il sélectionne le plus petit exposant trouvé dans la décomposition de et .

4. Calcul du PGCD à partir des facteurs communs

Le PGCD est alors le produit des facteurs premiers communs, chacun élevé au plus petit exposant trouvé dans les décompositions respectives de et .

5. Affichage de la décomposition du PGCD

a) L'algorithme affiche la décomposition en facteurs premiers du PGCD avec les facteurs communs et leurs exposants.

b) Il affiche ensuite la valeur numérique du PGCD.

Dans cet algorithme, On va utiliser deux fonctions :

Algorithme calcul_pgcd
Debut
     saisie_ab()
     Ecrire('PGCD(',a,' , ',b, ')= ',pgcd(a,b))
Fin

Algorithme calcul_pgcd

Debut

saisie_ab()

Ecrire('PGCD(',a,' , ',b, ')= ',pgcd(a,b))

Fin

Déclaration des objets

Objet	Type / Nature
a	entier
b	entier

La procédure saisie_ab

Cette procédure saisit deux entiers m et n tel que 10≤a

Procedure saisie_ab():
Début
    Ecrire('donner un entier >=10') 
    lire (a) 
    Tant que n<10 faire 
       Ecrire('donner entre >=10') 
       lire (a) 
    Fin tant que
    
    Ecrire('donner un entier b tq b>'+a) 
    lire (b) 
    Tant que b<a faire 
       Ecrire('donner un entier b tq b>'+a) 
       lire (b) 
    Fin tant que  
 Fin

Procedure saisie_ab():

Début

Ecrire('donner un entier >=10')

lire (a)

Tant que n<10 faire

Ecrire('donner entre >=10')

lire (a)

Fin tant que

Ecrire('donner un entier b tq b>'+a)

lire (b)

Tant que b<a faire

Ecrire('donner un entier b tq b>'+a)

lire (b)

Fin tant que

Fin

Déclaration des objets

Objet	Type / Nature
a	entier
b	entier

La fonction pgcd

Cette fonction calcule le PGCD des deux entiers a et b

fonction pgcd(a:entier,b:entier):entier
Début
      p<-1
      i<-2
      Tant que (i<=a div 2) et (i<=b // 2) faire
          Si (a mod i==0) et (b mod i==0):
             a<-a div i
             b=b div i
             p<-p*i 
          Sinon
             i<-i+1
          Fin tant que
      Fin tant que
      retourner p 
Fin

fonction pgcd(a:entier,b:entier):entier

Début

p<-1

i<-2

Tant que (i<=a div 2) et (i<=b // 2) faire

Si (a mod i==0) et (b mod i==0):

a<-a div i

b=b div i

p<-p*i

Sinon

i<-i+1

Fin tant que

retourner p

Fin

Déclaration des objets

pentier

Objet	Type / Nature
i	entier
p	entier

Solution en Python

def saisie_ab() :
    global a,b
    a=int(input("donner un entier a>=10 "))
    while(a<10) :
      a=int(input("donner un entier b>=10  "))
      
    b=int(input('donner un entier b > '+str(a)+': '))
    while(b<=a) :
       b=int(input("donner un entier b > "+str(a)+': '))  
    
def pgcd(a,b):
     p=1
     i=2
     while (i<=a // 2) and (i<=b // 2):
           if (a % i==0) and (b % i==0):
                a=a // i
                b=b // i
                p=p*i                    
           else:
                i=i+1
      
     return p        

#programme principal
saisie_ab()
print('PGCD(',a,' , ',b, ')= ',pgcd(a,b))

def saisie_ab() :

global a,b

a=int(input("donner un entier a>=10 "))

while(a<10) :

a=int(input("donner un entier b>=10 "))

b=int(input('donner un entier b > '+str(a)+': '))

while(b<=a) :

b=int(input("donner un entier b > "+str(a)+': '))

def pgcd(a,b):

p=1

i=2

while (i<=a // 2) and (i<=b // 2):

if (a % i==0) and (b % i==0):

a=a // i

b=b // i

p=p*i

else:

i=i+1

return p

#programme principal

saisie_ab()

print('PGCD(',a,' , ',b, ')= ',pgcd(a,b))

Exécution du programme

Solution en Python et Designer QT

Pour créer une application en Python pour calculer le PGCD de deux entiers en utilisant Qt Designer pour l'interface graphique, suivez ces étapes :

1- Créer l'interface graphique avec Qt Designer

a- Ouvrez Qt Designer et créez un nouveau fichier de type Main Window.

b- Ajoutez ces widgets:

QLineEdit nommé 'a' pour entrer un entier >=10.

QLineEdit nommé 'b' pour entrer un entier b >a.

QPushButton nommé 'pgcd_bt' pour exécuter le module calcul_pgcd.

QLabel nommé 'msg' pour afficher un message d'erreur et le résultat du PGCD.

Enregistrez le fichier avec l'extension .ui, par exemple pgcd-interface.ui.

2- Créer le script Python pour l'application

Voici un exemple de script Python qui utilise l'interface graphique générée par Qt Designer.

from PyQt5.uic import loadUi
from PyQt5 import QtCore, QtGui
from PyQt5.QtWidgets import *
from PyQt5 import QtCore, QtGui, QtWidgets

app = QApplication([])
windows = loadUi ("pgcd-interface.ui")

def pgcd(a,b):
     p=1
     i=2
     while (i<=a // 2) and (i<=b // 2):
           if (a % i==0) and (b % i==0):
                a=a // i
                b=b // i
                p=p*i                    
           else:
                i=i+1
      
     return p        
    
def calcul_pgcd() :
  a = int(windows.a.text())
  b = int(windows.b.text())
  windows.msg.clear()
  if 10<=a<b :
    windows.msg.setText('PGCD('+str(a)+' , '+str(b)+ ')= '+str(pgcd(a,b)))
  else:
    windows.msg.setText('Veuillez saisir a et b tq 10<=a<b')    

windows.pgcd_bt.clicked.connect(calcul_pgcd)

windows.show()
app.exec_()