Discussion :

[Fabien3141]

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]

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]

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]

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]

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]

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