Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

python

Posté par
Liliana27
02-11-22 à 20:04

Bonjour à tous,

je dois écrire un algorithme affichant  les nombres de Mersenne premiers inférieurs à un million.

m=0
for n in range (1000):
        if m<1000000000:
                 print ("au rang", n, ":m=",m)
       m1=2**n-1

Je vous remercie.

Posté par
ty59847
re : python 02-11-22 à 20:19

As-tu testé ton programme ?
Est-ce que ce qu'il affiche est correct ?

Posté par
Liliana27
re : python 02-11-22 à 20:22

ouii mais ça n'affiche pas les nombres de Mersenne premiers, ça me les affiche tous

Posté par
mathafou Moderateur
re : python 02-11-22 à 20:31

Bonjour,
pour moi ce que tu as écrit affiche 1000 fois le nombre 0 !
et même en corrigeant la dernière ligne ce ne serait pas bon

et pourquoi, un tests sur un milliard ?? (d'une valeur m qui reste d'ailleurs à 0 tout le temps)

et puis 2**999 - 1 c'est largement plus (énormément plus) que 1 million !

quand tout ça sera corrigé de façon cohérente,
il va falloir ajouter un test de primarité...

Posté par
ty59847
re : python 02-11-22 à 20:34

Ok. Donc tu as corrigé un détail par rapport à ce que tu as posté.
Et effectivement, si on regarde ligne à ligne ce que fait ton programme, il n'y a aucune instruction pour tester si le nombre m est premier.
Et donc .... il faut ajouter un test pour vérifier si m est premier avant d'afficher m.
Autre truc, million, milliard... c'est pareil ?

Posté par
Liliana27
re : python 02-11-22 à 20:40

Oui je me suis trompée dans l'énoncé, on souhaite un nombre de Mersenne premier inférieur à un milliard.

Je ne sais pas comment ajouter un test de primarité.

Je sais bien que le programme paraît incohérent, cependant il fonctionne. Je ne sais pas comment le modifier car si j'enlève m=0 ça m'indique qu'il ya une erreur

Posté par
Liliana27
re : python 02-11-22 à 20:49

mathafou @ 02-11-2022 à 20:31

Bonjour,
pour moi ce que tu as écrit affiche 1000 fois le nombre 0 !
et même en corrigeant la dernière ligne ce ne serait pas bon

et pourquoi, un tests sur un milliard ?? (d'une valeur m qui reste d'ailleurs à 0 tout le temps)

et puis 2**999 - 1 c'est largement plus (énormément plus) que 1 million !

quand tout ça sera corrigé de façon cohérente,
il va falloir ajouter un test de primarité...


Cela serait vrai si j'avais utilisé la boucle while

Posté par
mathafou Moderateur
re : python 02-11-22 à 21:00

l'erreur ICI (sur le forum) est sur la dernière ligne

Liliana27 @ 02-11-2022 à 20:04


m=0
for n in range (1000):
   if m<1000000000:
      print ("au rang", n, ":m=",m)
   m1=2**n-1


m1 = 2**n - 1 est sans doute m = 2**n-1
(d'où la remarque de ty59847 "Donc tu as corrigé un détail par rapport à ce que tu as posté")

mais même en corrigeant ça, il affiche
au rang 0 m = 0
au rang 1 m = 0 (car il a calculé à la boucle d'avant m=2**0 - 1 = 1-1 = 0)
c'est faux m devrait être 2^1 - 1 = 1
ce décalage de un cran persiste jusqu'à la fin.

il faut calculer m au début de la boucle et pas à la fin

(et inutile de calculer jusqu'à 2^999 -1
la borne sur n peut être largement réduite !)

Posté par
Liliana27
re : python 02-11-22 à 21:21

Il faurdrait donc ajouter une variable compteur?

compteur=0
n=1
while compteur<1000000000:
          m=2**n-1
           if (le test de primalité queje n'arrive pas à trouver)
                  compteur=compteur+1
                   print ("au rang", n, ":m=",m)
            n=n+1

Posté par
mathafou Moderateur
re : python 02-11-22 à 21:49

mais non c'est bien m lui même qu'il faut tester :
par exemple :


n=1
m=1 # 2**1-1, 1ere valeur
while m<1000000000:
   if (le test de primalité que je n'arrive pas à trouver)
       print ("au rang", n, ":m=",m)
   n=n+1
   m=2**n-1 # valeur suivante


avec le for au lieu du while le problème était que le suivant était calculé avant l'incrémentation (implicite) de n, d'où le décalage

"le test de primarité"
le mieux est d'en faire une fonction à part entière

def isprime(a):
...

qui retourne True ou bien False.
elle contiendra elle même une boucle pour tester les diviseurs potentiels de a.
rappel a%d donne le reste de la division entière de a par d.

dans le programme principal on aura :
if isprime(m) :

Posté par
Liliana27
re : python 02-11-22 à 22:12

Je ne comprends pas vraiment dans quel ordre je dois tout mettre.

n=1
m=1
for n in range (100):
      if isprime(m):
            if (n%m) == 0:
                return False
       return True
       print ("au rang", n, ":m=",m)
   n=n+1
   m=2**n-1

Posté par
mathafou Moderateur
re : python 02-11-22 à 22:51

tu remplace juste ton baratin
"if (le test de primalité que je n'arrive pas à trouver)" par le vvrai test :
if isprime(m)

n=1
m=1
while m <1000000000:
   if isprime(m):
       print ("au rang", n, ":m=",m)
   n=n+1
   m=2**n-1


et il faut écrire à part la fonction isprime()

def isprime(a):
   tester tous les entiers  dans une certaine gamme
   si l'un d'eux divise a, a n'est pas premier : return False
   si  aucun ne divise a, a est premier : return True

c'est un algorithme à part entière à créer de toutes pièces
et à mettre entièrement avant le "programme principal" pour que cette fonction soit définie quand on s'en sert

on pourrait certes développer et inclure tout ce processus avec ses boucles et ses tests internes en lieu et place du simple if isprime(m)
mais
ça rendrait le programme illisible
ça ne satisferait pas au principe de base de découper un problème en taches élémentaires que l'on peut tester séparément.

Posté par
ty59847
re : python 02-11-22 à 22:51

Tu as cette fonction isprime() à ta disposition, parfait.

2 options.
1. Tu pars de ce que tu viens d'écrire en Python, et tu traduis chaque instruction en français.
Est-ce que ça te paraît bien.

2. Ecris, en français, une série d'ordres (d'instructions, verbes à l'impératif) , ou de petits bouts de phrase très simples, pour décrire le processus.

L'option 1, c'est pour vérifier si ce que tu as fait est bon, et continuer à partir de cette base.
L'option 2, c'est la démarche 'normale'. On a une demande, un exercice à faire. On décompose le traitement en étapes, décrites avec des mots de tous les jours.
On traduit 'mot-à-mot' chaque instruction en Python.

Posté par
mathafou Moderateur
re : python 02-11-22 à 22:59

"Tu as cette fonction isprime() à ta disposition".
ça m'étonnerait !
elle ne fait pas partie des bibliothèques standard de Python ..
il faut donc la faire soi-même
(ou la pomper ailleurs, voire même dans un autre exercice)

Posté par
ty59847
re : python 02-11-22 à 23:14

Soit...
Faisons simple. Faisons l'exercice en considérant qu'on a une boite noire nommée premier(m) qui nous renvoie Vrai ou Faux, selon que m est premier ou pas.
Ensuite, comment sera constituée cette boite noire, c'est un 2ème chantier.

Posté par
mathafou Moderateur
re : python 02-11-22 à 23:20

en fait on peut le trouver tout fait dans la bibliothèque sympy

donc

from sympy import isprime

n=1
m=1
while ...
   if isprime(m):
       print(...)
   n=n+1
   m = ...

et rien d'autre
mais ça dépendra de quel mouture de Python on dispose (de la présence ou pas de cette bibliothèque)
et c'est un peu longuet au démarrage (la taille de la bibliothèque, même si on ne se sert que d'une seule de ses fonctions)

en l'absence de la bibliothèque sympy, pas le choix : faut le coder soi-même comme déja dit

Posté par
Liliana27
re : python 03-11-22 à 22:46

Bonsoir,
en le codant moi-même cela donnerait:
n=0
m=2**n-1
for n in range (2,1000):
    for m in range (1000):
        if m%n == 0:
            print("m non premier")
            break
else:
    print ("m est premier")

Posté par
Liliana27
re : python 03-11-22 à 22:49

ty59847 @ 02-11-2022 à 23:14

Soit...
Faisons simple. Faisons l'exercice en considérant qu'on a une boite noire nommée premier(m) qui nous renvoie Vrai ou Faux, selon que m est premier ou pas.
Ensuite, comment sera constituée cette boite noire, c'est un 2ème chantier.

Justement après avoir trouvé le test de primalité je ne sais pas ce que je dois mettre ensuite, en faite j'ai l'impression de mélanger toutes les informations

Posté par
mathafou Moderateur
re : python 04-11-22 à 00:00

tester si un nombre m (ici un nombre de Mersenne) est premier ou pas, c'est une seule boucle : on
essaie de le diviser par "tous" les nombres plus petits
on ne modifie pas m lui même dans le boucle par une autre boucle sur m !

test UN nombre m = 2**n - 1:

(ici  sera m = 2**n - 1)

for d in range(truc) :  # lesquels ?
     # d car n est déja utilisé pour autre chose
     if m%d == 0:
         # m est divisible par d
         break # pas la peine de dire qu'il n'est pas premier
     # pas de else, else on continue juste la boucle for d 
# à la fin de la boucle for d il faut tester si on est sorti à cause du
# break ou si c'est parce qu'on est arrivé au bout :
if m%d!=0:
     # c'est parce qu'on est arrivé au bout, ce m  est premier
     print("au rang ",n," : M =",m)
    # ce print, c'est afficher ce nombre de Mersenne là car il est premier
# sinon rien à dire et rien à faire, ce nombre de Mersenne m n'est pas premier,
# on passe en silence au m suivant (au n suivant)


Et tout ça c'est à glisser tel quel dans la boucle de génération des nombres de Mersenne (de tous les nombres de Mersenne) exactement là où tu avais écrit

if (test de primarité que ne ne sais pas faire):

sans rien changer d'autre de la boucle principale par ailleurs.

Bon, cette façon de faire (écrire la boucle de test de primarité à l'intérieur même de la boucle générale) est comme je l'ai déja dit "sale"
mais fais le quand même, on verra après comment le rendre plus propre avec une fonction

j'ai écrit range(truc) parce que ton "1000" ne tient pas debout
avec des nombres de Mersenne allant jusqu'à 1 milliard, il peut y avoir des diviseurs (le plus petit diviseur) bien plus grand que 1000 !
en fait ce range dépend de m
en réfléchissant, on en déduit qu'il suffit d'aller jusqu'à racine de m

Posté par
mathafou Moderateur
re : python 04-11-22 à 00:04

PS :
en réfléchissant, on en déduit qu'il suffit d'aller jusqu'à racine de m
et qu'il ne faut surtout pas dépasser m-1
parce que quel que soit m, m est divisible par m !

Posté par
Liliana27
re : python 04-11-22 à 00:35

Je vous remercie pout toutes ces explications et votre patience.

Si j'ai bien compris cela donne donc:

n=1
m=1                                   # 2**1-1, 1ere valeur
while m <32000:        # puisque racine de 1 milliard est environ égale à 32000
   if for n in range(1000):
    if m%d==0:
        break
    if m%d!==0:
    print("au rang",n,":M=",m)
   n=n+1
   m=2**n-1                                    # valeur suivante

Posté par
mathafou Moderateur
re : python 04-11-22 à 01:32

ton indentation n'est pas claire
de plus "if for" ça n'existe pas
c'est uniquement for
le if est fait à la fin ; c'est le "if : print ..." final

de plus tu n'as pas compris que la génération des nombres de Mersenne se fait (doit se faire, c'est l'énoncé !) jusqu'à un milliard
while m < 1000000000:

mais que pour chacun , le test de primarité doit essayer des diviseurs d au moins jusqu'à racine de ce m, et au plus jusqu'à ce m - 1

for d in range(1000) ne peut pas fonctionner
d'abord il va essayer d = 0 (une division par 0 !)
alors que tu avais bien écrit correctement for d in range(2, maxi)

mettre ce maxi à 1000 fixe ne marchera pas non plus parce que avec un m qui vaudrait par exemple 7 il va essayer d = 7 (c'est bien <1000, non ?) et 7 est divisible par 7, prétendant au final que 7 n'est pas premier !

il FAUT un maxi qui dépend de la valeur de m

par exemple, for d in range (2, m) va marcher car il s'arrête à m-1 inclus et n'essaiera jamais de diviser m par m.

par contre si m est très grand (de l'ordre de plusieurs millions) il essaiera des millions de diviseurs d pour ce seul m là
le programme va durer des plombes !
for d in range (2, sqrt(m)) est douteux car sqrt(m) n'est pas un entier, et de plus il s'arrête avant si sqrt(m) est entier
ainsi il prétendrait que le carré d'un nombre premier est premier !
on aboutit ainsi à la boucle correcte :
for d in range(2,int(sqrt(m)+1))

reste de toute façon que le seul juge du fonctionnement d'un programme est de le faire tourner effectivement sur Python !
et ... ça ne marche pas, je suis désolé, j'ai fait une erreur.

en effet d n'est connu que à l'intérieur de la boucle for d
une fois qu'on en est sorti, d est inconnu et le 2ème test final sur d impossible
cela complique la chose ; il faut utiliser un "drapeau" (une simple variable) que l'on mettra à True ou à False pour dire à l'extérieur, depuis l'intérieur de la boucle, si on est passé ou pas par le break

le test de primarité (dans cette variante "sale" où il est mis directement inclus dans le programme lui-même) devient donc

n=1
m=1     # 2**1-1, 1ere valeur
while m <1000000000: 
   # ici commence le test de primarité
   estPremier = True # suppose qu'il l'est
   for n in range(2;int(sqrt(m)+1)):
      if m%d==0:
         estPremier = False # change d'avis, en fiat il ne l'est pas
         break
   # fin du test, le résultat est donné par le if qui suit :
   if estPremier:
       print("au rang",n,":M=",m)
   n=n+1
   m=2**n-1   # valeur suivante

programme testé OK à un léger détail près : le nombre 1 n'est pas un nombre premier
facile à corriger

Posté par
mathafou Moderateur
re : python 04-11-22 à 01:43

"programme testé OK"
hum, erreur de copier collé

c'est bien sûr for d in range(2, int(sqrt(m)+1)):

Posté par
Liliana27
re : python 04-11-22 à 21:43

Justement le but de l'exercice est que cela prenne du temps puisque la question suivante est "donner le temps mis par votre ordinateur"

Posté par
mathafou Moderateur
re : python 04-11-22 à 21:50

... le but étant que ce temps soit le plus court possible, pas le plus long possible

Posté par
Liliana27
re : python 04-11-22 à 22:16

mathafou @ 04-11-2022 à 01:32

ton indentation n'est pas claire
de plus "if for" ça n'existe pas
c'est  uniquement for
le if est fait à la fin ; c'est le "if : print ..." final

de plus tu n'as pas compris que la génération des nombres de Mersenne se fait (doit se faire, c'est l'énoncé !) jusqu'à  un milliard
while m < 1000000000:

mais que pour chacun , le test de primarité doit essayer des diviseurs d  au  moins jusqu'à racine de ce m, et au plus jusqu'à ce m - 1

for d in range(1000) ne peut pas fonctionner
d'abord il va essayer d = 0 (une division par 0 !)
alors que tu avais bien écrit correctement  for d in range(2, maxi)

mettre ce maxi à 1000 fixe ne marchera pas non plus parce que avec un m  qui vaudrait par exemple 7 il va essayer d = 7 (c'est bien  <1000, non ?) et 7 est divisible  par 7, prétendant au final que 7 n'est pas premier !

il FAUT un maxi qui dépend de la valeur de m

par exemple, for d in range (2, m) va marcher car il s'arrête à m-1 inclus et n'essaiera jamais de diviser m par m.

par contre si m est très grand (de l'ordre de plusieurs millions) il essaiera des millions de diviseurs d pour ce seul m là
le programme va durer des plombes !
for d in range (2, sqrt(m)) est douteux car sqrt(m) n'est pas un entier, et de plus il s'arrête avant si sqrt(m) est entier
ainsi il prétendrait que le carré d'un nombre premier est premier !
on aboutit ainsi à la boucle correcte :
for d in range(2,int(sqrt(m)+1))

reste de toute façon que le seul juge du fonctionnement d'un programme est de le faire tourner effectivement sur Python !
et ... ça ne marche pas, je suis désolé, j'ai fait une erreur.

en effet d n'est connu que à l'intérieur de la boucle for d
une fois qu'on en est sorti, d est inconnu  et le 2ème test final sur d impossible
cela complique la chose ; il faut utiliser un "drapeau" (une simple variable) que l'on mettra à True ou à False pour dire à l'extérieur, depuis l'intérieur de la boucle, si on est passé ou pas par le break

le test de primarité (dans cette variante "sale" où il est mis directement inclus dans le programme lui-même) devient donc

n=1
m=1     # 2**1-1, 1ere valeur
while m <1000000000: 
   # ici commence le test de primarité
   estPremier = True # suppose qu'il l'est
   for n in range(2;int(sqrt(m)+1)):
      if m%d==0:
         estPremier = False # change d'avis, en fiat il ne l'est pas
         break
   # fin du test, le résultat est donné par le if qui suit :
   if estPremier:
       print("au rang",n,":M=",m)
   n=n+1
   m=2**n-1   # valeur suivante

programme testé OK à un léger détail près : le nombre 1 n'est pas un nombre premier
facile à corriger


Donc je ne dois pas mettre de test de primalité au début? Je ne comprends pas qu'est-ce qu'est la variable "Est premier", elle ne marche pas su Python

Posté par
mathafou Moderateur
re : python 04-11-22 à 23:04

avec la correction que j'ai apportée le 04-11-22 à 01:43
(d et pas n et une virgule et pas un point virgule dans le range()

copier coller exact : (testé et garanti)

# pour sqrt()
from math import *
# M1 = 1 n'est pas un nombre premier, le test le prétendrait premier !
# on commence à M2 = 3
n=2
m=2**n-1
while m <1000000000:
   # ici commence le test de primarité
   estPremier = True # suppose qu'il l'est
   for d in range(2,int(sqrt(m)+1)):
      if m%d==0:
         estPremier = False # change d'avis, en fait il ne l'est pas
         break
   # fin du test, le résultat est donné par le if qui suit :
   if estPremier:
       print("au rang",n,": M=",m)
   n=n+1
   m=2**n-1   # valeur suivante


(copier coller et par retaper avec des fautes de frappe, hein)

et le test de primarité c'est cette partie là qui est bien déja incluse dedans :

   # ici commence le test de primarité
   estPremier = True # suppose qu'il l'est
   for d in range(2,int(sqrt(m)+1)):
      if m%d==0:
         estPremier = False # change d'avis, en fait il ne l'est pas
         break
   # fin du test, le résultat est donné par le if qui suit :
   if estPremier:


estPremier est une variable comme une autre, au même titre que n, m, d etc
elle n'a pas un statut particulier
j'ai expliqué à quoi elle sert le 04-11-22 à 01:32
Citation :
d n'est connu que à l'intérieur de la boucle for d
une fois qu'on en est sorti, d est inconnu et le 2ème test final sur d impossible
cela complique la chose ; il faut utiliser un "drapeau" (une simple variable) que l'on mettra à True ou à False pour dire à l'extérieur, depuis l'intérieur de la boucle, si on est passé ou pas par le break

Posté par
Liliana27
re : python 04-11-22 à 23:25

J'ai fait un copier coller (j'utilise le logiciel Thonny):


from math import*
n=2
m=2**n-1
while m <1000000000:
      estPremier = True
   for d in range(2,int(sqrt(m)+1)):
      if m%d==0:
         estPremier = False
         break
   if estPremier:
       print("au rang",n,": M=",m)
   n=n+1
   m=2**n-1  

Mais il m'est indiqué :

"IndentationError: unindent does not match any outer indentation level"

Posté par
mathafou Moderateur
re : python 05-11-22 à 00:04

tu vois bien que l'indentation n'est pas la même que la mienne,
d'où l'erreur chez toi.
d'ailleurs tu n'as pas fait juste copier coller car tu as supprimé les commentaires (les # )
et ce faisant tu as modifié l'indentation par inadvertance.

testé par copier coller exact tel quel (CTRL-C sur PC) depuis mon message de 23:04 vers EduPython (PyScripter) sur mon PC
et aussi vers https://replit.com/languages/python3

Posté par
Liliana27
re : python 05-11-22 à 00:54

Ah d'accord je comprends mieux ! Je ne savais pas qu'enlever les commentaires avait une influence sur le programme (j'a vu quelques notions de programmation en seconde mais pas en première). Je vous remercie infiniment pour toutes vos explications !

On obtient les résultats :

au rang 2 : M= 3
au rang 3 : M= 7
au rang 5 : M= 31
au rang 7 : M= 127
au rang 13 : M= 8191
au rang 17 : M= 131071
au rang 19 : M= 524287

Posté par
mathafou Moderateur
re : python 05-11-22 à 09:21

ce n'est pas enlever les commentaires qui est le problème, mais que en faisant ça tu as par erreur aussi enlevé ou laissé trainer un espace de l'indentation de la ligne qui suivait !

bref, tu as vu que pour calculer ça, ça va très vite (une fraction de seconde)

si on pousse les calculs plus loin que 1 milliard on trouve
au rang 31 : M= 2147483647
(très rapide)
puis il rame pendant presque une demi-heure avant de donner le suivant
au rang 61 : M= 2305843009213693951

le problème est le test de primarité qui est "très lent" (c'est tout relatif)
et qui pour prouver juste que M61 est premier il a exécuté 1.5 milliard de test par tous les nombres de 2 à 1518500249 !
les premiers précédents étaient plus modestes (seulement 46000 pour M31)
éliminer les non premiers est par contre très rapide car les diviseurs effectifs sont généralement petits

bref au dela de M31 le programme tel quel est inutilisable

il faut utiliser des tests de primarité plus puissants
(et d'ailleurs éliminer d'office sans même les tester le nombres qui par la théorie ne peuvent pas être premier)

de telles améliorations sont largement au delà de ce qui est demandé ici

par contre je reviendrais tout à l'heure (longueur du message) sur une amélioration tout de même importante : l'utilisation et la définition de fonctions
(parce que c'est une technique générale partout)


Posté par
mathafou Moderateur
re : python 05-11-22 à 11:24

avec les hoquets du site , plus le temps maintenant, on verra plus tard

Posté par
Liliana27
re : python 05-11-22 à 11:58

D'accord, je vous remercie pour votre aide !

Posté par
mathafou Moderateur
re : python 07-11-22 à 11:47

Maintenant qu'on a un truc qui marche, on va le faire "propre"
ceci répond très exactement à ton inquiétude de tout mettre en vrac on ne sait où

on va séparer le problème en sous problèmes plus simples qu'on étudie séparément
- générer les nombres de Mersenne (tous)
- tester si un nombre (quelconque) est premier ou non.
c'est l'application stricte de la règle générale quand on s'attaque à un problème assez complexe :
le découper en tâches plus simples sous forme de "boites noires"
on étudie ainsi séparément chacune des tâches élémentaires et séparément l'agencement entre elles de ces "boites noires"

de la même façon que quand on écrit
x = a*cos(t) ou r = sqrt(x**2+y**2) on fait appel à une fonction cosinus ou racine carrée
cette fonction fait des calculs internes "assez compliqués" et elle est écrite, définie, quelque part une fois pour toutes
dans ce cas là dans une bibliothèque, le module math
les bibliothèques de Python contiennent des milliers de telles fonctions

mais surtout en ce qui concerne notre problème on peut définir soi même des fonctions !!

ainsi on peut définir soi-même une fonction estPremier(a) qui teste si un nombre quelconque a est premier ou pas
à défaut d'en trouver une toute faite dans une bibliothèque

et utiliser (appeler) cette fonction au sein du programme de génération des nombres de Mersenne

le programme complet aura ainsi la structure suivante (tout et tel quel) :


# définition de la fonction testant si a est premier ou pas
# elle renverra (return) True ou False (vrai ou faux)
def estPremier(a):
    if a < 2:
        return False # ni 1 ni 0 ne sont premiers
    # sinon (else inutile à cause du return qui fait quitter la fonction)
    d=2
    # avec cette boucle while on évite l'appel à sqrt()
    while d*d <= a:
        if a%d==0: # si ce d divise a
            return False
        d=d+1
    # aucun diviseur trouvé
    return True
    
# désormais on peut utiliser (appeler) cette fonction autant qu'on veut
# pour tester si un nombre quelconque est premier ou pas
# on va l'utiliser pour filtrer les nombres de Mersenne :

# boucle de génération de tous les nombres de Mersenne < 1 milliard
n = 1
m = 2**n - 1 # 1er nombre de Mersenne
while m < 1000000000:
    # test si ce nombre m convient
    # en utilisant la fonction estPremier() définie au dessus
    if estPremier(m):
        print("au rang",n,": M =",m)
    # sinon on ignore ce m là
    # dans tous les cas on passe au suivant
    n = n+1
    m = 2**n - 1
# terminé

l'ensemble est beaucoup plus clair (surtout si on écrit des commentaires !) car on a séparé les problèmes.
On peut tester la fonction estPremier indépendamment :
on essaie dans la console estPremeier(2), estPremier(4), estPremier(17), estPremier(25) etc en imaginant des nombres qui risqueraient de poser problème comme des petits nombres, le carré d'un nombre premier, ce carré plus ou moins 1, un grand nombre premier, un produit de deux grands nombres premiers jumeaux etc)

on peut même penser ces deux problèmes séparément dans l'ordre qu'on veut
c'est à dire très exactement ce que disait ty59847 le 02-11-22 à 23:14
Citation :
Faisons simple. Faisons l'exercice en considérant qu'on a une boite noire nommée premier(m) qui nous renvoie Vrai ou Faux, selon que m est premier ou pas.
Ensuite, comment sera constituée cette boite noire, c'est un 2ème chantier.
(même si dans le programme complet cela devra être écrit avant, dans la conception on peut le penser après

et j'avais déja donné cette structure le 02-11-22 à 21:49

Posté par
alb12
re : python 07-11-22 à 14:19

salut,
super bien expliqué et surtout conforme à ce qui est raisonnablement exigible en terminale
Pour ma part concernant la deuxieme partie j'aurais ecrit une fonction qui renvoie la liste des nombres de Mersenne premiers.
Par exemple:


def estPremier(a):
    """retourne True si a est premier False sinon"""
    # local d
    if a < 2:
        return False # ni 1 ni 0 ne sont premiers
    d=2
    while d*d <= a:
        if a%d==0: # si d divise a
            return False
        d=d+1
    return True

# désormais on peut utiliser (appeler) cette fonction autant qu'on veut
# pour tester si un nombre quelconque est premier ou pas
# on va l'utiliser pour filtrer les nombres de Mersenne :

def MersennePremiers(N):
    """renvoie la liste des nombres de Mersenne premiers inf à N"""
    # local L,k,m
    L=[]
    k = 1
    m = 1
    while m <= N:
    # test si ce nombre m convient
    # en utilisant la fonction estPremier définie au dessus
        if estPremier(m):
            L.append(m) #on ajoute m à la liste L
        k = k+1
        m = 2**k - 1
    return L

Quelques essais en console:

>>> estPremier(103)
True
>>> estPremier(1045)
False
>>> estPremier(1)
False
>>> estPremier(2)
True
>>> MersennePremiers(10**9)
[3, 7, 31, 127, 8191, 131071, 524287]
>>> MersennePremiers(131071)
[3, 7, 31, 127, 8191, 131071]
>>> MersennePremiers(131070)
[3, 7, 31, 127, 8191]
>>> help(estPremier)
Help on function estPremier in module __main__:

estPremier(a)
    retourne True si a est premier False sinon

>>> help(MersennePremiers)
Help on function MersennePremiers in module __main__:

MersennePremiers(N)
    renvoie la liste des nombres de Mersenne premiers inf à N

Posté par
alb12
re : python 09-11-22 à 19:04

j'ai oublié le rang dans la fonction MersennePremiers


from sympy import *

def estPremier(a):
    """retourne True si a est premier False sinon"""
    # local d
    if a < 2:
        return False # ni 1 ni 0 ne sont premiers
    d=2
    while d*d <= a:
        if a%d==0: # si d divise a
            return False
        d=d+1
    return True

def MersennePremiers(N):
    """renvoie la liste des nombres de Mersenne premiers inf à N"""
    # local L,k,m
    L=[]
    k = 1
    m = 1
    while m <= N:
        if estPremier(m):
            L.append([k,m]) # on ajoute [k,m] à la liste L
        k = k+1
        m = 2**k - 1
    return L


En console:

>>> MersennePremiers(10**12)
[[2, 3],
 [3, 7],
 [5, 31],
 [7, 127],
 [13, 8191],
 [17, 131071],
 [19, 524287],
 [31, 2147483647]]
>>> isprime(2147483647)
True
>>> isprime(2305843009213693951)
True

Posté par
mathafou Moderateur
re : python 09-11-22 à 23:28

Si on importe isprime() de sympy il est inutile de programmer soi-même une fonction estPremier qui sera forcément moins performante, et de beaucoup.

on n'a pas parlé de la question "quelle est la durée de ce programme" parce que jusqu'à M31 = 2 milliards et quelque, ça s'exécute en une fraction ,de seconde, même avec ce estPremier() très naïf là (tester tous les entiers jusqu'à racine de M... )

pour mesurer le temps de calcul on peut le faire avec la fonction
perf_counter() du module time :

from time import perf_counter # pour mesurer le temps d'exécution

# pour utilisation d'un test de primarité perso (et naif)
def premier(a):
    if a < 2: # ni 0 ni 1 ne sont premiers
        return False
    d = 2
    while d*d <= a:
        if a%d == 0:
            return False # divisible par d
        d = d+1
    return True # aucun diviseur

# nombres de Mersenne premiers < 2**65-1 = 36893488147419103231
# range(1,30) 2**30 - 1 est le plus petit nombre de Mersenne > 1 milliard
t0 = perf_counter()
for n in range(1,65): # range(1,30) pour l'exo
    m = 2**n-1 # valeur pour ce n là
    if premier(m): 
        print("au rang",n,": M =",m)
t1=perf_counter()
print("durée = ",t1-t0,"secondes")

résultat :
*** Console de processus distant Réinitialisée ***
au rang 2 : M = 3
au rang 3 : M = 7
au rang 5 : M = 31
au rang 7 : M = 127
au rang 13 : M = 8191
au rang 17 : M = 131071
au rang 19 : M = 524287
au rang 31 : M = 2147483647
au rang 61 : M = 2305843009213693951
durée = 784.3321676989999 secondes

c'est à dire environ un quart d'heure à tourner avant de terminer. !
et il est totalement impossible avec une telle durée d'exécution exponentiellement croissante d'aller au dela . (jusqu'au suivant M89)

si j'utilise un test de primarité efficace (à savoir la fonction isprime() de sympy à la place de premier(m) écrit soi même,
la durée d'exécution à la même taille devient en millièmes de seconde !!
durée = 0.0015395549999999147
et on peut aller plus loin en un temps raisonnable :

avec range(1, 100) pour aller jsuqu'à 299 - 1
au rang 2 : M = 3
au rang 3 : M = 7
...
au rang 19 : M = 524287
au rang 31 : M = 2147483647
au rang 61 : M = 2305843009213693951
au rang 89 : M = 618970019642690137449562111
durée = 0.005143326000000226 secondes
(4 millisecondes de calcul)

voire range(1,1000) permettant d'aller jusqu'à M607, un nombre de 183 chiffres, en moins d'une seconde de calcul !
...
au rang 607 : M = 531137992816767098689588206552468627329593117727031923199444138200
4035598608522427391625022652292856688893294862465010153465793376527072394095199
78766587351943831270835393219031728127
durée = 0.6881727639999997 secondes

pour aller encore plus loin , il faut utiliser un test de primarité spécialement conçu pour les nombres de Mersenne : le test de Lucas-Lehmer
(durée simplement proportionnelle au nombre de chiffres !)

tout ceci
y compris l'utilisation de listes et de mettre le programme principal lui-même dans une fonction retournant une liste, et de définir des fonction d'aide (disant ce que fait chaque fonction)
est totalement en dehors de ce qui est demandé (attendu) dans l'exo. !
c'est juste se faire plaisir en exhibant ce qu'on sait faire

edit : découpe en tranche ici de M607 pour éviter que ça dépasse de l'écran

Posté par
alb12
re : python 10-11-22 à 08:07

les fonctions et les listes sont des attendus du programme.
A mon avis ces notions sont essentielles.

Posté par
carpediem
re : python 10-11-22 à 08:53

salut

j'ai suivi de loin ...

pour répondre à alb12 au passage et dans un premier temps :

vu l'intitulé de la question on peut décider d'afficher "à la volée" un nombre de Mersenne dès qu'on en rencontre un ou on peut décider d'utiliser une liste (afin de les conserver pour une utilisation ultérieure éventuellement) mais ça ne me semble pas une obligation

pour en venir au script et aux interventions pertinentes de mathafou et sans aller chercher des fonctions puissantes de python ou des tests "super" performants on peut tout de même optimiser un algo naïf en remarquant qu' un nombre de Mersenne  est impair de par sa définition et donc tester la divisibilité uniquement par des nombres impairs en commençant par 3 (comme on le fait en général avec des nombres (premiers) quelconques où on teste la divisibilité par 2 à part puis après on ne considère que les impairs)

une division par deux des essais de la boucle de test de divisibilité donne un gain de temps substantiel ... du moins avec une calculatrice (qu'utilisent généralement les élèves)

je ne sais pas si c'est énorme avec un ordi mais peut-être mathafou pourra-t-il nous dire avec python sur un ordi ce que ça donne



PS :j'ai bien aimé ton idée du test sur d qui n'utilise pas la racine carrée

Posté par
mathafou Moderateur
re : python 10-11-22 à 11:07

Bonjour,
tout à fait
je m'étais cantonné à ce qu'il était raisonnable d'exiger
comme le montre alb12 on peut aller effectivement plus loin.
même en restant "dans le programme"

un test de primarité en ne testant que les diviseurs impairs est une amélioration "classique" et même sans "remarquer que les Mn sont impairs", pour une fonction générale testant un nombre quelconque.
on commence par tester (dans la fonction) si le nombre est impair,
avant d'entrer dans la boucle avec d = 3 et une progression d = d+2
diviser le nombre de tests par deux (donc la durée d'exécution car cette boucle est la composante majeure du temps d'exécution) est une amélioration notable et à peu de frais

quant au test avec sqrt ou bien d*d chacun a ses avantages et inconvénients

for d in range(3,int(sqrt(a)+1),2) ...
(boucle sur les nombres impairs seuls, un pas de 2 dans le range)
l'expression du for (range) est évaluée une fois pour toutes en début de cette boucle
avantage : diminue le temps d'exécution
mais il génère une liste effective en mémoire de toutes les valeurs de d
inconvénient : taille mémoire utilisée pour les calculs

d=3
while d*d <= a ...
          d=d+2

avantage
le calcul du produit d*d reste dans les nombres entiers et est plus rapide que le calcul de sqrt
taille mémoire réduite car les valeurs de d sont calculées une par une et pas toutes mises dans une liste
inconvénient :
d*d est calculé à chaque boucle

Posté par
mathafou Moderateur
re : python 10-11-22 à 12:15

oups
non, la liste créée par range est bien définie une fois pour toutes au début de la boucle, mais en mémoire seul un élément à la fois est stocké. l'argument de taille mémoire n'est pas pertinent.

Posté par
alb12
re : python 10-11-22 à 17:28

pour info et



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !