Calculateur de nombres premiers.

**Fabien3141** · 24/08/2008, 22h20

Bonjour,
Je me suis mis un petit programme pour calculer les nombres premiers de 1 à X.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#!/usr/bin/env python
# -*- coding: latin-1 -*-
import time
from math import sqrt
 
#J'utilise psycho pour plus de rapidité
if __name__ == '__main__':
    # Import Psyco if available
    try:
        import psyco
        psyco.full()
    except ImportError:
        pass
 
listep=[2,3]
n_a_tester=5
print "\n*** PREM'S a0.10 ***\n"
limite=input("Calculer jusqu'à : ")
a=3
 
def test (n_a_tester):
    n_list=len(listep)
    for i in range(n_a_tester):
 
        if n_a_tester%listep[i]==0:
            break
        elif (i+1)==n_list or n_a_tester<listep[i]**2:
            listep.append(n_a_tester)
            return n_a_tester
        elif n_a_tester%listep[i]!=0:
            i+=1
 
start=time.ctime()
while a<limite :
    test (n_a_tester)
    n_a_tester+=1
    a+=1
finish=time.ctime()
 
print "Start: ", start, "\nFinish:", finish
# On écrit les nombres P dans le fichier listea.html
nombre_prems=len(listep)
nombre_prems=str(nombre_prems)
print "Ecriture du fichier"
fichier = open("listea.html", "w")
fichier.write("<h3>Nombre de NP trouvés : ")
fichier.write(nombre_prems)
fichier.write("</h3><br />")
fichier.write(start)
fichier.write("<br />")
fichier.write(finish)
fichier.write("<br /><br/>")
fichier.write(str(listep))
fichier.close()
print "Écriture terminée, fin du programme \n"

Pour info, voici se que j'obtiens :
Test avec 50'000'000 NP : 5m 12
avec 100'000'000 NP :12m 51

Alors le "problème" c'est que je n'arrive pas à utiliser les 2 processeurs même avec "Parallel Python", pourrait on m'aider SVP

?
Et autrement comment trouvez vous mon application ? Qu'en pensez vous ?

Merci

++

Fab

**Matthieu Brucher** · 25/08/2008, 18h27

Tu devrais tester avec Numpy à la place de la boucle for, sur le principe du crible d'Eratosthène.
Parallel Python, je ne connais trop, je dois dire. En revanche, sur Python normal, c'est logique, un seul thread pour l'interpréteur à la fois. En revanche, si tu passes par Numpy, ça marchera mieux

Et tu devrais utiliser timeit pour chronométrer tes exécution, c'est fait pour ça

**Fabien3141** · 26/08/2008, 15h22

Ok, merci des conseilles par contre j'ai pas vraiment compris comment utiliser Numpy...
Et pour le crible d'Eratosthène, le script sur wikipedia est plus lent que le mien;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
#!/usr/bin/env python
def crible(tableau):
        if not tableau or tableau[0]**2 > tableau[-1]: return tableau
        return tableau[:1] + crible([i for i in tableau if i%tableau[0]])
 
print crible(range(2,5000))

Comme souvent avec les fonctions récursives, le code obtenu est concis mais peu efficace pour de grandes valeurs de N.

**Matthieu Brucher** · 26/08/2008, 15h32

Faut pas écrire le crible sous forme récursive

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
def crible(max):
  tableau = numpy.ones((max,), dtype = numpy.int32) # on construit un tableau indicateur avec des 1 pour nombre premier
  nb_max = int(math.sqrt(max))
  for i in range(2, nb_max):
    tableau[2*i-1::i] = 0

qqch du style (non testé) pour obtenir les nombre premiers entre 1 et max (la première valeur dans le tableau correspond au nombre 1). Et après, un numpy.sum là-dessus te donne le nombre de nombres premiers. Je pense que ce sera plus rapide.

**tyrtamos** · 26/08/2008, 18h46

Bonjour,

Je me suis un peu amusé à cela, et ce que j'ai fait est ici: http://python.jpvweb.com/mesrecettes...mbres_premiers.

Pour n=100,000,000, j'ai 2mn 45sec.

A mon avis, la seule manière de faire mieux est d'enregistrer la liste des nombres premiers antérieurement trouvés et de les utiliser. En ayant un fichier disque en accès direct, la lecture est très rapide.

Tyrtamos

**Fabien3141** · 26/08/2008, 23h53

Envoyé par tyrtamos

A mon avis, la seule manière de faire mieux est d'enregistrer la liste des nombres premiers antérieurement trouvés et de les utiliser. En ayant un fichier disque en accès direct, la lecture est très rapide.

Ouais et faudrait partager ça avec des ordis en réseaux

Faudrait qu'on se fasse une application open source qui fasse ça

Bon le problème c'est qu'il faudrait programmer en assembleur je pense pour que ce soit vraiment le top...
Enfin si quelqu'un est partant, je suis là; j'ai toujours voulu aider la science

**tyrtamos** · 27/08/2008, 09h11

Bonjour,

Avant d'en arriver au calcul distribué, il y a une méthode simple pour se constituer un fichier de nombres premiers: utiliser le fait que son propre ordinateur est rarement chargé à plus de 10% en moyenne.

On peut ainsi avoir un programme python qui se lance au démarrage de l'ordinateur (Windows ou Linux), lit le fichier des nombres premiers antérieurement trouvés, identifie le dernier trouvé, et commence à chercher les suivants. En donnant à ce programme une faible priorité, on peut travailler normalement sur l'ordinateur. On peut aussi arrêter le programme et le redémarrer à tout moment sans rien perdre. Ainsi, pendant des mois, le fichiers des nombres premiers s'accroit tout seul.

J'ai essayé cela pendant quelques semaines, et j'ai obtenu un fichier texte (1.3Go!) de nombres premiers jusqu'à 2 749 707 173. Je n'ai pas encore mis ce programme sur mon site, mais si tu es intéressé, je peux le faire. Certains sites web proposent même des fichiers de nombres premiers à télécharger (http://primes.utm.edu/lists/small/millions/).

Une fois obtenu le fichier texte des nombres premiers, on peut le transformer en fichier en accès direct. On peut alors chercher dedans par dichotomie pour savoir si un nombre donné est premier, ou pour essayer de factoriser un nombre en nombres premiers. J'ai pu constater qu'une telle recherche par dichotomie était très rapide.

Mais bon, c'est amusant, mais ce n'est pas la bonne méthode pour factoriser les codes de cryptage RSA-2048: c'est beaucoup trop long... Pour mémoire, la factorisation du RSA-640 a demandé plus de 5 mois de calcul avec 30 CPU. Alors, pour le RSA-2048, il faudra compter en millions d'années... Pourtant, j'ai pu constater que python avec l'accélérateur psyco n'était pas loin de la rapidité du C pour ce genre d'algorithme. Mais même en assembleur, cette méthode sera trop lente. Il faut recourir à des méthodes heuristiques. Il y a pas mal de sites web qui parlent de cela.

Tyrtamos

**Fabien3141** · 27/08/2008, 15h03

OK, merci beaucoup pour tes détails.
Mais qu'y aurait-il comme méthodes heuristiques ?
J'ai entendu parler du "Test de primalité de Lucas-Lehmer" ainsi que les nombres premiers de Mersenne...
Et autrement si tu es d'accord de publier ta source, très volontiers.

Mais autrement j'ai une question un peu bête... si je veux faire un très grand nombre premier, au feeling, par exemple (2^3468493)-1, pour le tester je suis obligé de tester tout les nombres premiers avant lui (ou depuis 2 jusqu'à sa racine carrée) ou y a t'il un autre test fiable à 100% ?

**tyrtamos** · 28/08/2008, 07h23

Bonjour,

Pour l'instant, je ne connais que les méthodes "brutales", mais il y a des sites qui parlent des autres méthodes, par exemple:

http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9

http://fr.wikipedia.org/wiki/Cat%C3%...primalit%C3%A9

http://villemin.gerard.free.fr/ThNbDemo/Primalit.htm

http://www.cryptosec.org/Test-de-pri...ler-Rabin.html

http://www.mersenne.org/prime.htm

http://cermics.enpc.fr/polys/oap/node91.html

Etc...

On peut même trouver des livres comme ceux d'Edouard Lucas (1842-1891). Par exemple:

http://tony.reix.free.fr/EdouardLuca...DESNOMBRES.PDF

Utilise google avec simplement "primalité" et, pour la version anglaise, "primality".

En dehors de la méthode brutale, de nombreux "tests de primalité" cherchent justement à tester si un nombre n est "probablement premier" sans tester avec tous les nombres premiers inférieurs à racine de n.

Pour ce qui concerne la cryptologie RSA, et les méthodes de factorisation pour casser ses codes:

http://www.jscoron.fr/thesis/node4.html

Ok pour publier mes sources: laisse-moi un peu de temps et je te signalerai sur ce fil de discussion quand elles seront en ligne.

Tyrtamos

**Fabien3141** · 29/08/2008, 19h11

Super !
Merci encore pour tes informations supplémentaire.

Et merci de partager tes sources, c'est vraiment sympa !
A bientôt

**clic4** · 30/08/2008, 14h39

Envoyé par Fabien3141

Mais autrement j'ai une question un peu bête... si je veux faire un très grand nombre premier, au feeling, par exemple (2^3468493)-1, pour le tester je suis obligé de tester tout les nombres premiers avant lui (ou depuis 2 jusqu'à sa racine carrée) ou y a t'il un autre test fiable à 100% ?

Salut !

Les nombres sous la forment de 2^n -1 sont appelés nombres de Mesrenne, du nom d'un moine de l'ordre des Minimes au début du XVIIe siècle. Pour qu'un tel nombre soit premier, il faut que son exposant soit lui même premier. (tiré de Les dossiers de la recherche, n°20, août 2005).

Pour info, le plus grand nombre premier que l'on connaisse actuellement (prouvé donc) est 2^32 582 657-1... de quoi calculer un petit moment

**monnomamoi** · 30/08/2008, 16h08

Envoyé par clic4

Salut !
Pour qu'un tel nombre soit premier, il faut que son exposant soit lui même premier.

Oui, c'est une condition nécessaire, mais malheureusement pas suffisante (ex: 2^11 - 1).

Mais si " log2(nombre+1) = entier pas premier ", alors tu peux être sûr que "nombre" n'est pas premier

**tyrtamos** · 17/09/2008, 21h39

Bonjour,

Comme promis, mon code est ici: http://python.jpvweb.com/mesrecettes...mbres_premiers.

Amuse-toi bien!

Tyrtamos

Calculateur de nombres premiers.

Calcul scientifique Python

Discussions similaires

Partager

Partager