Fabriquez votre fichier de nombres premiers

Une fois qu'on a une fonction qui calcule une liste des nombres premiers, on se dit:

• finalement, je devrais pouvoir en calculer autant que je voudrais si je les stockais dans un fichier

• et puis je n'utilise pas toujours mon ordinateur à 100%: il y a de la place pour une “tâche en arrière plan”

• mais il faudrait que je puisse arrêter le programme sur demande, et qu'il puisse repartir de la dernière liste au redémarrage.

Le code suivant sert à cela!

Il y avait tout de même un petit problème. Je voulais utiliser l'accélérateur psyco (voir sur ce site: http://python.jpvweb.com/mesrecettespython/psyco), mais lorsque l'accélérateur est en fonctionnement, il n'écoute pas le clavier, et donc aucun “Ctle-C” ne l'arrête. Or, pour que le fichier en cours reste valable, il faut trouver un moyen pour générer une interruption à la demande de façon qu'une instruction de fermeture du fichier puisse être exécutée. Ce que, bien sûr, l'arrêt sauvage de la console ou le reboot du PC ne saurait faire. De plus, je tiens à ce que ça fonctionne en “multiplateforme” (Windows + Linux au moins, éventuellement Mac).

Dans mes recherches, j'ai été surpris de constater que Python n'avais ni “getch()” (saisir le caractère tapé au clavier) ni “kbhit()” (savoir si une touche a été appuyée). Il a donc fallu “bricoler”:

• des fonctions getch_win() (pour Windows) et get_lin() (pour Linux) qui sont censées attendre et renvoyer le caractère tapé au clavier. La fonction getch() elle-même pointe sur l'une ou l'autre de ces fonctions selon la plateforme.

• un thread clavier pour compenser l'absence de kbhit(): ce thread peut attendre qu'un utilisateur tape sur le clavier sans ralentir le calcul

• un simple test dans la boucle de calcul pour terminer la boucle si l'utilisateur tape Ctle-C.

Et… ça marche!

Pour utiliser ce programme, il faut:

• se placer dans une console (cmd pour Windows, shell pour Linux),

• se placer avec la commande “cd” dans le répertoire dans lequel il y a le programme (je l'ai appelé trouvepremiers.py)

• lancer le programme par “python trouvepremiers.py”

Au démarrage, le programme détecte psyco et l'utilise s'il est présent.

Il cherche ensuite s'il y a un fichier “premiers.txt” dans le même répertoire

• si oui, il le charge en mémoire

• si non, il en fabrique un nouveau.

Ensuite, il ouvre le fichier en ajout, et y ajoute les nombres premiers au fur et à mesure qu'il les trouve.

Un Ctle-C ou n'importe quelle autre erreur arrête le programme, mais en fermant correctement le fichier.

Avec psyco, le calcul est très rapide compte tenu de la quantité de calcul réalisé. Sous Linux (swap=2Go), au bout de 3 ou 4 heures seulement, je suis arrivé à “2 176 005 437”, avec un fichier de 1Go!

Sous Windows XP, j'ai été bloqué à “1 339 088 837” pour “MemoryError”: il n'a pas supporté une liste aussi longue de nombres. Il est clair que même avec Linux, ce calcul échouera lorsque l'OS refusera la liste des nombres premiers en mémoire. Il faudra alors utiliser d'autres méthodes.

D'ici là, rien ne vous empêche de laisser tourner ce programme en tâche de fond pendant plusieurs mois…

Voilà le code. Il est auto-documenté:

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
import os
import sys
import threading
 
# si l'accélérateur "psyco" est présent, l'utiliser:
try:
    import psyco
    psyco.full()
    print
    print u"accélérateur psyco trouvé et utilisé"
except ImportError:
    pass
 
####################################################################
# fonctions multiplateformes renvoyant le caractère d'une touche pressée du clavier
#
def getch_win():
    return msvcrt.getch()
 
def getch_lin():
    fd = sys.stdin.fileno()
    old_settings = termios.tcgetattr(fd)
    try:
        tty.setraw(fd)
        ch = sys.stdin.read(1)
    finally:
        termios.tcsetattr(fd, termios.TCSADRAIN, old_settings)
    return ch
 
def getch_autre():
    return None
 
####################################################################
class Clavier(threading.Thread):
    """thread clavier pour pouvoir arrêter avec Ctle-C, même avec psyco"""
 
    def __init__(self):
        threading.Thread.__init__(self)
        self.quit = False
 
    def run(self):
        while True:
            car = getch()
            if ord(car)==3:
                self.quit = True
                break  # =fin du thread
 
    def quitter(self):
        return self.quit
 
####################################################################
def trouvepremiers(fichier, p):
    """trouve de nouveaux nb 1er qui s'ajoutent aux précédents"""
 
    # calcul du 1er nb à essayer
    n = p[-1]+2
 
    # ouverture en ajout du fichier des nombres premiers
    f=open(fichier,'a')
 
    # calcul de tous les nb premiers suivants à partir de n
    try:
        while True:
            i=0
            while True:
                if p[i]*p[i]>n:
                    # => on a trouvé un nouveau nombre premier
                    p.append(n)
                    f.write("%s\n" % n)
                    break
                if (n%p[i])==0:
                    # => on a trouvé un diviseur: le nb n'est pas 1er
                    break
                i+=1
            n+=2
            if clavier.quitter():
                raise KeyboardInterrupt ("Arret du calcul sur demande")
 
    except:
        f.close()
        print
        print "%s" % sys.exc_info()[1]
        print
 
####################################################################
if __name__ == "__main__":
 
    # Calcul du nom du fichier des nombres 1er avec son chemin
    fichier = os.getcwd() + os.sep + "premiers.txt"
    print
    print u"Fichier des nombres premiers:", fichier
 
    # initialisation
    n=0
    p=[]
 
    # si le fichier existe déjà, charger son contenu
    if os.path.exists(fichier):
        try:
            f=open(fichier,'r')
            for line in f:
                p.append(int(line.rstrip("\r\n")))
            f.close()
        except:
            print
            print u"erreur d'ouverture ou de lecture du fichier existant"
            sys.exit()
        if len(p)>=3:
            n=p[-1]
            # si le fichier n'a pas le bon format, arrêter
            if p[2]!=5:
                print
                print u"erreur: mauvais format du fichier. Le renommer pour le recréer"
                sys.exit()
 
    # si le fichier n'existe pas, ou est vide, ou que sa dernière valeur est <5, le créer ou le recréer
    if n<5:
        print
        print u"création ou re-création du fichier"
        try:
            f=open(fichier,'w')
            f.write("2\n3\n5\n")
            f.close()
        except:
            print
            print u"erreur de création ou de re-création du fichier"
            sys.exit()
        p=[2,3,5]
        n=5
 
    print
    print u"dernier nombre premier calculé:", n
 
    # mise en place du mécanisme d'arrêt par Ctle-C, compatible avec psyco
    if sys.platform=="win32":
        import msvcrt
        getch = getch_win
    elif sys.platform=="linux2":
        import tty, termios
        getch = getch_lin
    else:
        getch = getch_autre
    clavier = Clavier()
    clavier.setDaemon(True)
    clavier.start()
 
    # lancement du calcul des nombres premiers suivants
    # arrêt par Ctle-C ou par n'importe quelle autre erreur: l'erreur est affichée
    trouvepremiers(fichier, p)