Nombre premier sûr – Bac Pratique 2015 [ Algorithme + Python ]
Sujet bac informatique pratique 2015 (Bac scientifique)
Un nombre M est dit nombre premier sûr s’il est un nombre premier de la forme 2*p+1 avec p un nombre premier.
Exemples : Si M=11, alors M est un nombre premier sûr. En effet, 11 est premier et il peut s’écrire sous la forme 2*p+1 ou p=5 qui est un nombre premier.
Si M=31, alors M n’est pas un nombre premier premier sûr. En effet 31 est premier et il peut s’écrire sous la forme 2*p+1 ou p=15 qui n’est pas un nombre premier.
N.B : Un nombre est premier s’il est divisible que par 1 et par lui-même. (1 n’est pas premier)
On se propose d’écrire un programme Phyton qui permet de :
1- Remplir un tableau T par n entiers > 2 (10 ≤ n ≤ 45).
2- Trier dans l’ordre croissant les éléments premiers sûrs du tableau T suivis du reste des éléments sans tri.
3-Afficher le tableau T résultant.
Exemple : Pour n=10 et le tableau T suivant :
Solution Algorithmique
Remplir le tableau T avec n entiers :
Remplir un tableau T avec n entiers aléatoires supérieurs à 2, où 10≤n≤4510.
Vérifier si un nombre est premier :
Créer une fonction pour vérifier si un nombre donné est premier (c'est-à-dire divisible uniquement par 1 et lui-même).
Vérifier si un nombre est un nombre premier sûr :
Pour chaque élément du tableau T, vérifier si c'est un nombre premier sûr :
Un nombre M est premier sûr s'il est premier et qu'il existe un nombre premier p tel que M=2∗p+1.
Trier les nombres premiers sûrs :
Récupérer tous les nombres premiers sûrs et les trier dans l'ordre croissant.
Conserver le reste des éléments sans les trier :
Les éléments qui ne sont pas des nombres premiers sûrs doivent rester dans le tableau sans changement.
Afficher le tableau final :
Afficher le tableau T avec les nombres premiers sûrs triés en premier, suivis du reste des éléments non triés.
Dans cet algorithme, on va utiliser trois fonctions et trois fonctions:
Algorithme du programme principal
|
1 2 3 4 5 6 7 8 |
Algorithme Nombre_premier_sur Debut n<-saisie_taille() Ecrire('remplissage du tableau t') remplir(t,n) partitionner(t,n) afficher(t,n) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
| t | tableau de 50 entiers |
La fonction saisie_taille
Cette procédure saisit la taille n du tableau tel que 10 ≤ n ≤ 45
|
1 2 3 4 5 6 7 8 9 10 |
Procedure saisie_taille(n:entier):entier Début Ecrire("donner un entier entre 10 et 45: ") lire(n) Tant que (n<10) ou (n>45) faire Ecrire("donner un entier entre 10 et 45: ") Lire(n) Fin tant que retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir
Cette procédure remplit un tableau de taille n par des entiers > 2.
|
1 2 3 4 5 6 7 8 9 10 11 |
Procedure remplir(@t:tab,n:entier) Début Pour i de 0 à n-1 faire Ecrire("donner elt N°"+i+'>2: ') lire(t[i]) Tant que t[i]<=2 faire Ecrire("donner elt N°"+i+'>2: ') lire(t[i]) Fin tant que Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La procédure trie
Cette procédure trie un tableau de taille n dans un ordre croissant en utilisant la méthode tri par sélection.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Procedure trie(@t:tab,n:entier) Début Pour i de 0 à n-2 faire minimum<-i Pour j de i+1 à n-1: Si (t[minimum] > t[j]) alors minimum<-j Si (minimum != i) alors x<-t[minimum] t[minimum]<-t[i] t[i]<-x Fin si Fin si Fin pour Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| minimum | entier |
La fonction test_premier
Cette fonction teste si un entier est premier ou non.
|
1 2 3 4 5 6 7 8 |
Fonction test_premier(n:entier):booleen Début i<-2 Tant que (n mod i !=0 ) et (i<= n div 2) faire i<-i+1 Fin tant que retourner (i> n div 2) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La fonction premier_sur
Cette fonction vérifie si un entier est premier sûr.
|
1 2 3 4 5 6 7 8 9 10 11 |
Fonction premier_sur(n:entier):booleen Début Si (test_premier(n)) alors p<- n div 2 Si (test_premier(p)) alors retourner Vrai Sinon retourner Faux Sinon retourner Faux Fin |
La procédure partitionner
Cette procédure met les éléments au début du tableau puis il les trie dans un ordre croissant.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Procédure partitionner(@t:Tab;n:entier) Début cp<-0 j<-0 Pour i de 1 à n-1 faire Si (premier_sur(t[i])) alors Tant que (premier_sur(t[j])) alors j=j+1 Fin tant que Si ((non(premier_sur(t[j]))) et (i>j)) faire x<-t[j] t[j]<-t[i] t[i]<-x cp=cp+1 Fin si Fin si Fin pour trie(t,cp) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| cp | entier |
| i | entier |
| j | entier |
| x | entier |
La procédure afficher
Cette procédure affiche les éléments du tableau de taille n.
|
1 2 3 4 5 6 7 |
Procedure remplir(t:tab,n:entier) Début Ecrire('le tableau apres la transformation') Pour i de 0 à n-1 faire Ecrire(t[i] Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
Solution en Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
from numpy import array t=array([int()]*50) #declaration du tableau des entiers def saisie_taille() : n=int(input("donner un entier entre 10 et 45: ")) while(n<10) or (n>45) : n=int(input("donner un entier entre 10 et 45: ")) return n def remplir(t,n): for i in range (n) : t[i]=input("donner elt N°"+str(i)+'>2: ') while(t[i]<=2): n=int(input("donner elt N°"+str(i)+'>2: ')) def trie(t,n): for i in range(n-1): minimum =i for j in range(i+1,n): if (t[minimum] > t[j]): minimum=j if (minimum != i) : x=t[minimum] t[minimum]=t[i] t[i]=x def test_premier(n): i=2; while (n % i !=0 ) and (i<= n // 2): i=i+1 return (i> n // 2) def premier_sur(n): if (test_premier(n)): p= n // 2 if (test_premier(p)) : return True else: return False else: return False def partitionner(t,n): cp=0 j=0 for i in range(1,n): if (premier_sur(t[i])): while (premier_sur(t[j])): j=j+1 if ((not(premier_sur(t[j]))) and (i>j)): x=t[j] t[j]=t[i] t[i]=x cp=cp+1 trie(t,cp) def afficher(t,n): print('le tableau apres la transformation') for i in range(n): print('t['+str(i)+']='+str(t[i])) #programme principal n=saisie_taille() print('remplissage du tableau t') remplir(t,n) partitionner(t,n) afficher(t,n) |
Exécution du programme
Solution en Python et Designer QT
Pour créer une application en Python pour remplir un tableau T par n entiers > 2 (10 ≤ n ≤ 45) et trier dans l’ordre croissant les éléments premiers sûrs du tableau T suivis du reste des éléments sans tri 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é 'ch' pour entrer les entiers > 2.
QPushButton nommé 'remplir_bt' pour exécuter le module createTab afin de remplir le tableau à partir de la chaine 'ch'.
QLabel nommé 'tab_label' pour afficher les éléments du tableau T.
QPushButton nommé 'bt_partition' pour placer les nombres premiers sûrs au début du tableau.
QPushButton nommé 'bt_trie' pour trier dans l’ordre croissant les éléments premiers sûrs du tableau T suivis du reste des éléments sans tri.
QLabel nommé 'msg' pour afficher les messages d'erreur
Enregistrez le fichier avec l'extension .ui, par exemple SIERPINSKI-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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
from PyQt5.uic import loadUi from PyQt5 import QtCore, QtGui from PyQt5.QtWidgets import * from PyQt5 import QtCore, QtGui, QtWidgets from numpy import array t=array([str]*100) app = QApplication([]) windows = loadUi ("tabtab-2.ui") # Fonction qui supprime des espaces de la chaine des carcatères def supprimer_espaces (ch) : while(ch[0]==' '): # elimnier tous les espaces au début de la chaine ch=ch[1:len(ch)] while(ch[len(ch)-1]==' '): # elimnier tous les espaces a la fin de la chaine ch=ch[0:len(ch)-1] while (ch.find(' ')>0): ch=ch.replace(" ", " ") # remplacer les doubles espaces apar un seul espace return ch # Procedure qui remplit un tableau par des entiers a partir d'une chaine des caractère def createTab(): ch = windows.ch.text() global n # pour la taille di tableau if ch=="": windows.msg.setText("Veuillez remplir la chaîne") else: windows.msg.clear() # effacer le message d erreur ch= supprimer_espaces(ch) i=0 j=0 ch1='' test=True # parcourir les caracteres de la chaine while((i<len(ch)) and (test) and (('0'<=ch[i]<='9') or (ch[i]==' '))): if ('0'<=ch[i]<='9'): ch1=ch1+ch[i] if ((ch[i]==' ') or (i==len(ch)-1)) : t[j]=int(ch1) ch1='' test=(t[j]>2) j=j+1 i=i+1 if (i<len(ch)) or (test==False) : windows.msg.setText("La chaine doit contenir des entiers >2") else : if 10<=j<=45: # test du taille du tableau n=j tab='' for k in range (j) : tab=tab+ 't['+str(k)+']= '+ str(t[k])+ '\n' #afficher les elements du tableau windows.tab_label.setText(tab) else: windows.msg.setText("Le nbr des elements doit etre entre 10 et 45") def trie(): for i in range(cp-1): minimum =i for j in range(i+1,cp): if (t[minimum] > t[j]): minimum=j if (minimum != i) : x=t[minimum] t[minimum]=t[i] t[i]=x tab='' for k in range (n) : tab=tab+ 't['+str(k)+']= '+ str(t[k])+ '\n' #afficher les elements du tableau windows.tab_label.setText(tab) def test_premier(n): i=2; while (n % i !=0 ) and (i<= n // 2): i=i+1 return (i> n // 2) def premier_sur(n): if (test_premier(n)): p= n // 2 if (test_premier(p)) : return True else: return False else: return False def partitionner(): global cp cp=0 j=0 for i in range(1,n): if (premier_sur(t[i])): while (premier_sur(t[j])): j=j+1 if ((not(premier_sur(t[j]))) and (i>j)): x=t[j] t[j]=t[i] t[i]=x cp=cp+1 tab='' for k in range (n) : tab=tab+ 't['+str(k)+']= '+ str(t[k])+ '\n' #afficher les elements du tableau windows.tab_label.setText(tab) windows.remplir_bt.clicked.connect ( createTab ) windows.bt_partition.clicked.connect ( partitionner ) windows.bt_trie.clicked.connect ( trie ) windows.show() app.exec_() |
Exécution du programme
1) Remplir le tableau par des entiers > 2
2) Placer les nombres premiers sûrs au début du tableau.
3) Trier dans l’ordre croissant les éléments premiers sûrs du tableau T suivis du reste des éléments sans tri.
Vous pouvez voir aussi :
1) des exercices sur les chaînes des caractères
2) des exercices sur les tableaux
3) des sujets Bac pratique
4) des sujets Bac théorique
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
