Crible d'eratostene liste

Version imprimable

bonjour,

Il y a un bug dans la console, il est écrit :
"RuntimeError: maximum recursion depth exceeded in cmp"

Code:

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
 
liste_entiers = [];
 
entier_max = input("saisir un entier : ");
 
for i in range(1, entier_max +1):
	liste_entiers.append(i);
 
def suppr_multiples(liste, num):
 
	if num > len(liste)/2:
		return liste;
 
	go_on = False
 
	for i in range(len(liste)):
		if liste[i] > num:
			if liste[i]%num == 0:
				liste[i] = 0;
 
	while go_on != True:
		if liste[num] == 0:
			num += 1
		else:
			go_on = True
 
	suppr_multiples(liste, num);
 
suppr_multiples(liste_entiers, 2);

J'ai bien regardé, je ne vois pas d'où ça peut venir, avez-vous une idée ?

Merci

15/05/2011, 17h29
kango

bonjour,

tu as atteint la limite de la pile d'appel de Python (elle est de 1000). pour augmenter cette limite voir:

http://docs.python.org/library/sys.h...recursionlimit

Salut, ton code comporte un bug quelque part, qui le fait récurser (!) indéfiniment…

En voici une version fonctionnelle, et plus efficace je pense ;)

Code:

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
entier_max = int(input("saisir un entier : "))
 
# Une liste-comprehension est bien plus élégante ici…
liste_entiers = [i for i in range(1, entier_max+1)]
 
def suppr_multiples(liste, num):
    if num > len(liste)/2:
        return liste
 
    new_num = 0  # On va stocker ici le prochain nombre premier.
    # enumerate retourne un tuple (index_de_l’élément, élément).
    for i, el in enumerate(liste):
        if el > num:
            # Si num divise el, supprimer cet élément de la liste.
            if not el % num:
                del liste[i]
            # Sinon, si le nouveau nombre premier n’a pas encore été trouvé, c’est celui-ci*!
            elif not new_num:
                new_num = el
 
    # Petit test final…
    if not new_num or num > len(liste)/2:
        return liste
 
    return suppr_multiples(liste, new_num)
 
print(suppr_multiples(liste_entiers, 2))

15/05/2011, 19h46
Joe_Dupont

Merci a tous les 2. Tu es adorable MOnt29.
16/05/2011, 10h53
Captain'Flam

Juste comme ça :

Code:

liste_entiers = range(1, entier_max+1)

Ça marche aussi. :P
16/05/2011, 13h01
mont29

Citation:

Envoyé par Captain'Flam

Juste comme ça :

Code:

liste_entiers = range(1, entier_max+1)

Ça marche aussi. :P

Oulala, la honte… J’avais pas vu ça ! :oops:

Supprimer les éléments de la liste, c'est pas terrible; ça nécessite de décaler tous les éléments qui suivent. Utiliser un modulo pour chaque élément à chaque passe, c'est pas vraiment dans l'esprit du crible d'Eratosthène non plus.
J'utiliserais plutôt une liste de booléens:
Code:

1 2 3 4 5 6 def primes(n): liste = [True]*(n-1) for i,v in enumerate(liste): if v: yield i+2 liste[i::i+2] = [False] * (n//(i+2))
n//(i+2) c'est le nombre d'éléments dans le slice.

[EDIT] ou sans décaler les indices:
Code:

1 2 3 4 5 6 7 def primes(n): liste = [True]*(n+1) liste[0:2] = [False,False] # 0 and 1 are not primes for i,v in enumerate(liste): if v: yield i liste[i::i] = [False] * (n//i)

16/05/2011, 23h36
mont29

Ack ! Décidément, ce post malmène mon estime personnelle :oops: :calim2: :oops:

Bravo, dividee, ta solution est dix fois plus élégante – sans même parler des performances :mouarf:

Code:

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
import math
n=10000
premiers=[True]*n #a priori tous premiers
premiers[0]=False #0 n'est pas premier
premiers[1]=False # 1 non plus
racine=math.sqrt(n) #la borne pour les tests
 
# la méthode du crible
def eratosthene ():
    i=2
    while i <= racine:
        k=2
        while k*i<n:
            premiers[k*i]=False #tous les multiples de i ne peuvent être premiers, on raye
            k=k+1
        for j in range(i+1,n+1):# on repart avec le premier non rayé
            if premiers[j]:
                i=j
                break
 
def main():
    eratosthene()
    print [i for i in range(0,n) if premiers[i]]#affiche les premiers entre 1 et n
 
if __name__ == '__main__':
    main()

Arf j'avais raté cette optimisation. :oops: Merci Zavonen.
Code:

1 2 3 4 5 6 7 8 9 10 11 import math def primes(n): liste = [True]*(n+1) liste[0:2] = [False,False] # 0 and 1 are not primes racine = math.sqrt(n) for i,v in enumerate(liste): if v: yield i if i <= racine: liste[i::i] = [False]* (n//i)
[EDIT]
C'est étonnant; en CPython 2.7 mon code est nettement plus rapide que celui de Zavonen, avec pypy 1.5 c'est le contraire qui se produit.
Mon code est plus lent avec pypy qu'avec CPython, ce qui est plutôt atypique.
Je suppose que pypy n'implémente pas le slicing (ou l'assignation à des slices) efficacement.

Arf ! Les cadors de l’aglorithmique ont encore frappé !

Bon, je me suis un peu amusé à essayer d’optimiser prime, en ne testant que les nombres impaires (ça complique la gestion des indices, mais divise par deux la taille de la liste de booleans…) – mais étrangement, les seuls situations où b_primes est plus efficace sont pour les petits nombres (inférieurs à 1000), après c’est plus ou moins équivalent à primes…

Code:

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
56
57
58
59
60
61
62
63
64
import math, time
 
def b_primes(n):
    if n < 2:
        return
    yield 2
    racine = math.sqrt(n)
    liste = [True]*((n-1)//2) # only odd numbers, starting from 3.
    for i,v in enumerate(liste):
        if v:
            ri = (i*2)+3 # the real number.
            yield ri
            if ri <= racine:
                liste[i::ri] = [False] * (((n//ri)+1)//2)
 
def primes(n):
    liste = [True]*(n+1)
    liste[0:2] = [False,False]  # 0 and 1 are not primes
    racine = math.sqrt(n)
    for i,v in enumerate(liste):
        if v:
            yield i
            if i <= racine:
                liste[i::i] = [False]* (n//i)
 
def eratosthene(n):
    premiers=[True]*(n+1) #a priori tous premiers
    premiers[0]=False #0 n'est pas premier
    premiers[1]=False # 1 non plus
    racine=math.sqrt(n) #la borne pour les tests
    i=2
    while i <= racine:
        k=2
        while k*i<=n:
            premiers[k*i]=False # tous les multiples de i ne peuvent etre premiers, on raye
            k=k+1
        for j in range(i+1,n+2):# on repart avec le premier non raye
            if premiers[j]:
                i=j
                break
    return premiers
 
def main():
    n = int(input("saisir un entier : "))
 
    start = time.time()
    prems = eratosthene(n)
    res = [i for i in range(0,n+1) if prems[i]]
#    print(res)
    print "(eratosthene:", time.time()-start, "secondes)"
#    print("(eratosthene:", time.time()-start, "secondes)")
    start = time.time()
    res = [i for i in primes(n)]
#    print(res)
    print "(primes:", time.time()-start, "secondes)"
#    print("(primes:", time.time()-start, "secondes)")
    start = time.time()
    res = [i for i in primes(n)]
#    print(res)
    print "(b_primes:", time.time()-start, "secondes)"
#    print("(b_primes:", time.time()-start, "secondes)")
 
if __name__ == '__main__':
    main()

Tant que j’y étais, j’ai fait quelques tests de performance (eratosthene est très légèrement modifié, dans sa version originale il ne renvoyait pas n quand celui-ci est lui-même premier…).

Avec CPython2.6, primes (optimisé ou pas) est à peu près dix à trente fois plus rapide qu’eratosthene :

Code:

1
2
3
4
5
6
7
8
9
10
11
i7deb64@debian-i7-amd64:~$ python2.6 ./Bureau/test.py
saisir un entier : 10000
(eratosthene: 0.01739811897277832 secondes)
(primes: 0.0016078948974609375 secondes)
(b_primes: 0.0015871524810791016 secondes)
 
i7deb64@debian-i7-amd64:~$ python2.6 ./Bureau/test.py
saisir un entier : 1000000
(eratosthene: 4.95398187637 secondes)
(primes: 0.154949903488 secondes)
(b_primes: 0.159056901932 secondes)

Avec CPython3.2, eratosthene est plus de sept fois plus rapide, mais reste quand même quatre à cinq fois plus lent que primes (optimisé ou non). Au passage, on remarquera que pour une fois, python3.2 fait aussi bien, ou mieux, que python2.6 ;)

Code:

1
2
3
4
5
6
7
8
9
10
11
i7deb64@debian-i7-amd64:~$ python3.2 ./Bureau/test.py
saisir un entier : 10000
(eratosthene: 0.015298128128051758 secondes)
(primes: 0.0017778873443603516 secondes)
(b_primes: 0.001859903335571289 secondes)
 
i7deb64@debian-i7-amd64:~$ python3.2 ./Bureau/test.py
saisir un entier : 1000000
(eratosthene: 0.790053129196167 secondes)
(primes: 0.15732312202453613 secondes)
(b_primes: 0.14905619621276855 secondes)

Enfin, avec PyPy1.5, c’est eratosthene qui passe devant, il est à peu près cinquante pourcent plus rapide que primes, qui lui reste aussi performant que sous CPython (comme remarqué par dividee).

Code:

1
2
3
4
5
6
7
8
9
10
11
i7deb64@debian-i7-amd64:~$ ./PyPy/pypy-c-jit-43780-b590cf6de419-linux64/bin/pypy ./Bureau/test.py 
saisir un entier : 10000
(eratosthene: 0.0171141624451 secondes)
(primes: 0.00663113594055 secondes)
(b_primes: 0.00250196456909 secondes)
 
i7deb64@debian-i7-amd64:~$ ./PyPy/pypy-c-jit-43780-b590cf6de419-linux64/bin/pypy ./Bureau/test.py 
saisir un entier : 1000000
(eratosthene: 0.0981698036194 secondes)
(primes: 0.152928113937 secondes)
(b_primes: 0.147271156311 secondes)

En conclusion : alors que primes est à peu près constant quel que soit l’interpréteur utilisé, eratosthene voit ses performances varier d’un facteur cinquante entre CPython2.6 et PyPy1.5 !

On améliore les performances de mon programme en ne faisant pas appel à range qui construit une liste pour rien.
On peut également commencer la boucle interne (j) à i+2 au lieu de i+1 car on ne trouve jamais deux entiers premiers consécutifs.
On peut également ne pas faire un produit à chaque tour de boucle
Version améliorée et chronométrée :
résultat 0.007 s
version précédente 0.016 s

Code:

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
import time
 
def time_this(func):
    """The time_this decorator"""
 
    def decorated(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        print "Ran in", time.time() - start, "seconds"
        return result
    return decorated
 
import math
n=10000
premiers=[True]*n #a priori tous premiers
premiers[0]=False #0 n'est pas premier
premiers[1]=False # 1 non plus
racine=int(math.sqrt(n)) #la borne pour les tests
 
# la méthode du crible
@time_this
def eratosthene ():
    i=2
    while i <= racine:
        k=2
        h=(n-1)/i #pour ne pas recalculer un produit à chaque tour de boucle
        while k<=h:
            premiers[k*i]=False
            k+=1
        j=i+1 if i<3 else i+2 #après 2 et 3 plus de premiers consécutifs
        while not premiers[j]:
            j+=1
        i=j
 
def main():
    eratosthene()
 
 
 
if __name__ == '__main__':
    main()

Bonjour,

J'avais déjà travaillé le crible d'eratostene (http://python.jpvweb.com/mesrecettes...mbres_premiers), mais j'ai pu constater que le code de dividee était meilleur (merci dividee!).

Je suis reparti de ce code, et j'ai essayé de l'améliorer en diminuant le nombre de tests "if i<=racine":
- si on élimine dès le départ les nombres pairs, on ne teste ensuite qu'un nombre sur 2
- on peut séparer en 2 boucles, celle avant racine et celle après, puisque celle après la racine ne neutralise plus les multiples.

Par ailleurs, j'ai évité le "enumerate" pour ne pas créer des sous-listes avec les 2 boucles.

Voilà ce que ça donne:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 def eratostene(n): """Nb premiers <= n par crible d'eratostene""" liste = [False,False] + [True]*(n-1) liste[2::2] = [False]*(n//2) # on élimine déjà tous les nombres pairs premiers = [2] # 2 est un nombre premier racine = int(math.sqrt(n)) racine = racine + [1,0][racine%2] # pour que racine soit impair for i in xrange(3,racine+1,2): if liste[i]: premiers.append(i) liste[i::i] = [False]*(n//i) # on élimine i et ses multiples return premiers + [i for i in xrange(racine,n+1,2) if liste[i]]
Contrairement au code de dividee, la fonction renvoie la liste complète des nombres premiers (et pas un nombre à chaque appel). Pour faire des comparaisons de temps d'exécution, j'ai donc ajouté à la fonction de dividee le code nécessaire pour obtenir la même liste.

Avec n=100000000 (cent millions), on trouve les 5761455 nombres premiers en 8,6 secondes, ce qui est déjà impressionnant. Par rapport au code de référence, on gagne ainsi environ 30% par la diminution du nombre de tests.

Mais au delà (j'ai essayé 1 milliard), on obtient un "memoryError" à la création de "liste" dans la fonction. Ça me semble être la limite de ce genre d'algorithme.

Tyrtamos

17/05/2011, 14h42
Zavonen

@tyrtamos
J'ai des résultats voisins avec n=100000000 (temps 10s)
l'interprète pypy et ce processeur
résultat de cpuinfo sous ubuntu 10.04 LTS
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 15
model name : Intel(R) Pentium(R) Dual CPU E2220 @ 2.40GHz
stepping : 13
cpu MHz : 1203.000
cache size : 1024 KB
Pareil pour 1 milliard (manque de mémoire).

Les résultats de mon précédent message sont obtenus sous Python 2.7 32b, Win7 64b, cpu=Intel core I7, Ram=6Go.

Si quelqu'un est intéressé par la fonction qui renvoie le nb premier suivant à chaque appel, c'est facile avec yield:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def eratostene_iter(n):
    """Itérateur renvoie les nb premiers <= n par crible d'eratostene"""
    liste = [False,False] + [True]*(n-1)
    liste[2::2] = [False]*(n//2) # on élimine déjà tous les nombres pairs
    yield 2 # 2 est un nombre premier
    racine = int(math.sqrt(n))
    racine = racine + [1,0][racine%2] # pour que racine soit impair
    for i in xrange(3,racine+1,2):
        if liste[i]:
            yield i
            liste[i::i] = [False]*(n//i) # on élimine i et ses multiples
    for i in xrange(racine,n+1,2):
        if liste[i]:
            yield i

Tyrtamos

En utilisant le module bitarray, la consommation de mémoire est drastiquement diminuée. Une liste de booléens utilise 32 bits par éléments; un bitarray n'utilise qu'un seul bit.
Par exemple, pour n = 1000000000 (1 milliard), la consommation mémoire n'est que de 120 MB environ. La liste résultante utilise plus de mémoire que cela...

Je peux monter jusque 8*1e9 environ, mais sans la possibilité de stocker le résultat sous forme de liste (d'où l'intérêt du générateur).

C'est toutefois un peu plus lent qu'une liste de booléens.

Voici le code (sans les optimisations de tyrtamos):
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 import math from bitarray import bitarray def primes_bits(n): crible = bitarray(n+1) crible.setall(True) crible[0] = crible[1] = False # 0 and 1 are not primes racine = math.sqrt(n) for i,v in enumerate(crible): if v: yield i if i <= racine: crible[i::i] = False
Code peu de différent, en fin de compte.

18/05/2011, 08h10
tyrtamos

Bonjour,

Merci dividee! Manifestement, ça marche. Avec ton code et n=1 milliard, on obtient en 3 minutes les 50847534 nombres premiers inférieurs à n.

Pour info: j'ai eu un peu de mal à installer bitarray sur Windows. A partir des sources, je n'ai pas réussi: Unable to find vcvarsall.bat (manque compilateur microsoft?). Par contre, après avoir installé le binaire de setuptools (setuptools-0.6c11.win32-py2.7.exe), l'installation avec easy_install de la version '.egg' de bitarray a été facile.

Tyrtamos