Entiers homogènes – Bac Pratique 2015 [ Algorithme + Python ]

Algo et Python 06-09-24

110 0

Sujet bac informatique pratique 2015 (Bac scientifique)

Soit n et m deux entiers naturels, on dit que n et m sont homogènes s’ils admettent les mêmes facteurs premiers.

Exemples :

N=60 et M=90 sont homogènes, car ils ont les mêmes facteurs premiers qui sont 2, 3 et 5. En effet 60=2²*3*5 et 90=2*3²*5.

N=60 et M=420 ne sont pas homogènes, car ils n’ont pas les mêmes facteurs premiers. En effet 6=2²*3*5 et 420=2²*3*5*7

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 n et m (5≤nSolution Algorithmique

Pour déterminer si deux entiers naturels et (où $) sont homogènes, c'est-à-dire s'ils partagent les mêmes facteurs premiers, voici le principe de l'algorithme :$

Principe de l'algorithme :

1. Saisie des valeurs de $n$ et $m$ : L'utilisateur entre deux entiers naturels $n$ et $m$ tels que $.$

2. Extraction des facteurs premiers :

Pour chaque nombre et , on décompose ces nombres en facteurs premiers.

3. Comparaison des ensembles de facteurs premiers :

Comparer les ensembles de facteurs premiers de $n$ et $m$ .

Si les ensembles sont identiques, alors $n$ et $m$ sont homogènes, sinon ils ne le sont pas.

4. Affichage du résultat :

Afficher si les deux nombres sont homogènes ou non.

Détails de l'algorithme :

1. Entrée :

Lire et tels que $.$

2. Décomposition en facteurs premiers :

Pour chaque nombre i, effectuer la décomposition en facteurs premiers.

Par exemple, pour un nombre i, trouver tous les nombres premiers tels que divise .

3. Comparaison des facteurs premiers :

Comparer les ensembles des facteurs premiers trouvés pour et .

Si les ensembles sont égaux, les deux nombres sont homogènes.

4. Sortie :

Si les ensembles sont égaux, afficher que et sont homogènes.

Sinon, afficher qu'ils ne sont pas homogènes.

Dans cet algorithme, On va utiliser deux fonctions :

Algorithme du programme principal

Algorithme nombres_homogenes
Debut
     saisie_mn()
     Si produit_facteurs(n)=produit_facteurs(m)alors
        Ecrire(n+' et '+m+' sont homogenes')
     Sinon
        Ecrire(n+' et '+m+' ne sont pas homogenes');
     Fin si
Fin

Algorithme nombres_homogenes

Debut

saisie_mn()

Si produit_facteurs(n)=produit_facteurs(m)alors

Ecrire(n+' et '+m+' sont homogenes')

Sinon

Ecrire(n+' et '+m+' ne sont pas homogenes');

Fin si

Fin

Déclaration des objets

Objet	Type / Nature
n	entier
m	entier

La procédure saisie_mn

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

Procedure saisie_mn():
Début
    Ecrire('donner un entier >=5') 
    lire (n) 
    Tant que n<5 faire 
       Ecrire('donner entre >=5') 
       lire (n) 
    Fin tant que
    
    Ecrire('donner un entier m tq m>'+n) 
    lire (m) 
    Tant que m<n ou m>31000 faire 
       Ecrire('donner un entier m tq m>'+n) 
       lire (m) 
    Fin tant que  
 Fin

Procedure saisie_mn():

Début

Ecrire('donner un entier >=5')

lire (n)

Tant que n<5 faire

Ecrire('donner entre >=5')

lire (n)

Fin tant que

Ecrire('donner un entier m tq m>'+n)

lire (m)

Tant que m<n ou m>31000 faire

Ecrire('donner un entier m tq m>'+n)

lire (m)

Fin tant que

Fin

Déclaration des objets

Objet	Type / Nature
n	entier
m	entier

La fonction produit_facteurs

Cette fonction effectue la décomposition en facteurs premiers et retourne le produit de ces facteurs

fonction produit_facteurs(n:entier,m:entier):entier
Début
      p<-1
      j<-1
      i<-2
      Tant que (n>1) faire
        Si (n mod i==0) alors
           n=n div i
           Si (i!=j) alors
              p<-p*i
              j<-i
           Fin si
        Sinon
           i<-i+1
        Fin si
      Fin tant que
      retourner p
Fin

fonction produit_facteurs(n:entier,m:entier):entier

Début

p<-1

j<-1

i<-2

Tant que (n>1) faire

Si (n mod i==0) alors

n=n div i

Si (i!=j) alors

p<-p*i

j<-i

Fin si

Sinon

i<-i+1

Fin si

Fin tant que

retourner p

Fin

Déclaration des objets

Objet	Type / Nature
i	entier
j	entier
p	entier

Solution en Python

def saisie_nm() :
    global n,m
    n=int(input("donner un entier n>=5 "))
    while(n<5) :
      n=int(input("donner un entier n>=5  "))
      
    m=int(input('donner un entier m > '+str(n)+': '))
    while(m<n) :
       m=int(input("donner un entier m > "+str(n)+': '))  
    
def produit_facteurs(n):
     p=1
     j=1
     i=2
     while(n>1):
           if (n % i==0):
                n=n // i
                if (i!=j):
                     p=p*i
                     j=i
           else:
               i=i+1
     return p
     

#programme principal
saisie_nm()
if produit_facteurs(n)==produit_facteurs(m):
    print(str(n)+' et '+str(m)+' sont homogènes')
else:
    print(str(n)+' et '+str(m)+' ne sont pas homogènes');

def saisie_nm() :

global n,m

n=int(input("donner un entier n>=5 "))

while(n<5) :

n=int(input("donner un entier n>=5 "))

m=int(input('donner un entier m > '+str(n)+': '))

while(m<n) :

m=int(input("donner un entier m > "+str(n)+': '))

def produit_facteurs(n):

p=1

j=1

i=2

while(n>1):

if (n % i==0):

n=n // i

if (i!=j):

p=p*i

j=i

else:

i=i+1

return p

#programme principal

saisie_nm()

if produit_facteurs(n)==produit_facteurs(m):

print(str(n)+' et '+str(m)+' sont homogènes')

else:

print(str(n)+' et '+str(m)+' ne sont pas homogènes');

Exécution du programme

Solution en Python et Designer QT

Pour créer une application en Python pour déterminer si deux entiers naturels et (où $) sont homogènes 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é 'n' pour entrer un entier >=5.

QLineEdit nommé 'm' pour entrer un entier m >n.

QPushButton nommé 'homogene_bt' pour exécuter le module recherche_homogene.

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

Enregistrez le fichier avec l'extension .ui, par exemple parfait-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 ("homogene-interface.ui")

def produit_facteurs(n):
     p=1
     j=1
     i=2
     while(n>1):
           if (n % i==0):
                n=n // i
                if (i!=j):
                     p=p*i
                     j=i
           else:
               i=i+1
     return p
    
def recherche_homogene() :
  n = int(windows.n.text())
  m = int(windows.m.text())
  windows.msg.clear()
  if 5<=n<m :
    if produit_facteurs(n)==produit_facteurs(m):
        windows.msg.setText(str(n)+' et '+str(m)+' sont homogènes')
    else:
        windows.msg.setText(str(n)+' et '+str(m)+' ne sont pas homogènes');
  else:
     windows.msg.setText('Veuillez saisir n et m tq 5<=n<m')    

windows.homogene_bt.clicked.connect(recherche_homogene)

windows.show()
app.exec_()