Table des matières
Création d'une liste de nombre premiers
On veut créer, en vue de consultation, un fichier qui contient les premiers nombres premiers dans l'ordre croissant. On en mettra un par ligne. On commence par la création du fichier dans lequel on va rentrer soi-même les tout premiers. Le fichier est créé dans le dossier courant, que l’on peut connaître avec la commande os.getcwd. S'il ne convient pas on peut en changer, voir le cours.
Ouverture d'un fichier en écriture
L'exemple ci-dessous permet de créer le fichier avec les premiers nombres premiers.
#Création du fichier et premier remplissage
fich = open('liste_premiers.txt', 'w') # création du fichier pour écriture
fich.write('2\n') # le \n marque le passage à la ligne
fich.write('3\n')
fich.write('5\n')
fich.write('7\n')
fich.close()
L'option 'w' dans la fonction open permet d'indiquer que l'ouverture ce fait en mode écriture – write.
Un fichier ouvert doit être refermé ! En effet, quand on exécute open, Python demande au système d'exploitation (OS) de lui donner accès au fichier. C'est particulièrement important en mode écriture car l'OS va verrouiller le fichier pour empêcher un autre processus d'écrire dedans. Si on ne referme pas le fichier avec close, l'OS ne sait pas qu'il peut déverrouiller le fichier.
Lecture du contenu du fichier
On a ainsi les quatre premiers nombres premiers et si on veut voir le contenu de ce fichier on entre
fich = open ('liste_premiers.txt', 'r')
content = fich.read()
fich.close()
fich est un objet spécial représentant le fichier. Il ne faut pas confondre fich avec le contenu de fich qui est le texte contenu dans le fichier. On accède à ce texte avec read. Une fois que l'on a stocké le contenu de fich dans content, on peut refermer le fichier avec close.
Trouver de nouveaux nombres premiers
Pour rajouter des nombres premiers on utilise l'algorithme du crible d'Ératosthène : un nombre est premier si et seulement si il n'admet aucun diviseur premier inférieur ou égal à sa racine carrée.
On rappelle que 1 n’est pas premier ; le premier nombre premier est 2 et c'est le seul nombre premier pair. Ainsi pour rajouter p nombres premiers on ouvre liste premiers, on extrait la liste des nombres premiers déjà connus, on prend successivement les impairs strictement supérieurs au dernier nombre premier connu et on teste leur primalité avec la propriété donnée ci-dessus et en cas de succès on rajoute le nouveau nombre premier à la liste en l'écrivant dans une nouvelle ligne à la fin du fichier. On met tout cela dans une fonction ajout de paramètre p.
Au choix, on peut essayer d'écrire tout cela tout seul, ou recopier et traduire le pseudo-code suivant, en prenant le temps de le comprendre, voire en le modifiant si c'est pertinent. On rajoute la mesure du temps de
l'ajout à l’aide de la fonction time du module time.
importer module time
FONCTION ajout
ENTRÉE: p, int, nombre de premiers à ajouter
SORTIE: float, temps d'exécution en secondes
DÉBUT
enregistrer l'heure de début
soit content le contenu du fichier 'liste_premiers.txt'
soit lines le tableau obtenu en découpant content à tous les sauts de ligne '\n'
soit premiers le tableau contenu la conversion en int des items non vides de lines
soit N le nombre d'items dans premiers
soit last_p le dernier item de premiers
soit try_p = last_p + 2 le premier nombre à tester
TANT QUE le nombre d'items dans premiers < N + p, RÉPÉTER
soit success = True, marqueur qui passera à False si try_p a un diviseur
POUR CHAQUE prem DANS premiers FAIRE
SI prem divise try_p ALORS
success passe à False
interrompre la boucle
FIN
FIN
SI success est True ALORS
ajouter try_p au bout de premiers
FIN
ajouter 2 à try_p
FIN
ouvrir le fichier 'liste_premiers.txt' en ajout
POUR CHAQUE item DANS premiers à partir du rang, N FAIRE
convertir cet entier en texte
l'écrire dans le fichier en ajoutant '\n' à sa suite
FIN
fermer le fichier
enregistrer l'heure de fin
renvoyer la différence entre l'heure de fin et l'heure de début
FIN
Ce script a un défaut : supposez qu'on lance dans 2 consoles différentes, à peu près en même temps, la commande ajout(100000). Que va-t-il se passer ? Le premier appel lit le fichier, constate qu'on n'a que les premiers de 2 à 7, libère le fichier et commence à chercher. Le deuxième appel accède lui aussi au fichier et fait le même constat et se met à chercher. Quand il a terminé sa recherche, le premier appel ajoute les premiers 11, 13, … Le 2e appel attend que le premier appel ait terminé d'ajouter ses trouvailles puis ajoute les siennes, qui sont les mêmes… Pour éviter ce problème, on pourrait ouvrir le fichier en écriture dès le début et ne le fermer qu'à la fin de façon à verrouiller l'accès au fichier tout du long de la recherche.
Consultation de la liste
FONCTION affiche_liste():
DÉBUT
soit content le contenu de 'liste_premiers.txt'
soit lines le tableau obtenu en découpant L à tous les sauts de ligne '\n'
afficher le nombre d'items dans lines et lines
FIN
Avec affiche_liste() on a la liste des premiers nombres premiers connus.
Mise en œuvre
Il est temps de s'amuser et d'enrichir notre fichier, en essayant d'aller raisonnablement loin.
On peut en rajouter 500, 1000, etc. et on pourra constater que suivant le nombre N de nombres
premiers déjà calculés le temps d'exécution de ajout(p) augmente avec N , ce qui peut interroger
le mathématicien, la mathématicienne, et aussi l’informaticien, l’informaticienne mais pas forcément
pour les mêmes raisons.
On peut maintenant interroger notre fichier pour savoir si un nombre n est premier ou non (s'il est
dans la liste), pour connaître, dans le cas où il serait premier, son rang dans la liste des premiers
et inversement pour un rang p donné, retourner le p-ième nombre premier. L'intérêt étant que les
calculs sont faits une fois pour toutes et donc l'accès à l'information est plus rapide.
Écrire une fonction p_ieme_premier(p) qui retourne le p-ième nombre premier. Il faudra prévoir
le cas où p est trop grand pour la liste calculée soit, au choix, en répondant que le nombre est trop
grand pour l'état actuel des données, soit en rajoutant les nombres premiers nécessaires (les deux
versions sont intéressantes).
Écrire une fonction rang_premier(n) qui pour un entier n précise s'il est premier ou non – il faudra là encore gérer le dépassement comme ci-dessus – et, dans le cas où il est premier, donner son rang dans la liste des premiers déjà calculés.
Fréquence des nombres premiers
Ceci étant fait, on s'intéresse en mathématiques à la fréquence des nombres premiers, c'est-à-dire, si on note $\pi(n)$ le nombre de nombres premiers inférieurs ou égaux à $n$, on s'intéresse au quotient $\frac{\pi(n)}{n}$.
En utilisant la liste obtenue, on peut définir une fonction Python pi_premier(n) et considérer numériquement ou graphiquement la suite $\left(\frac{\pi(n)\,\ln(n)}{n}\right)_{n\geqslant 2}$ et on voit des choses que l’on interprète.
On sait qu'il y a de plus en plus de nombres premiers – l'ensemble des nombres premiers est infini – mais on voit qu'ils sont de plus en plus rares et on peut quantifier cette rareté progressive. C'est le célèbre théorème des nombres premiers que l'on découvre numériquement, visuellement, ici.