optimiser programme récursif nombres premiers

Version imprimable

salut à tous
j'ai écrit ceci qui marche bien :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
def liste_premiers(n):
    N={x for x in range(1,n+1)}
    r=int(sqrt(n))
    if (r<=10):
        N={2,3,5,7}
    else:
        for i in liste_premiers(r):
            x=0
            while (x<=n): #Crible d'Eratosthene
                if (x in N): N.remove(x)
                x+=i
    L=[x for x in N]
    return(L)

je me demande si c'est optimal et si on peut l'améliorer en termes de rapidité ou de fluidité
Vincent

17/03/2016, 08h51
VinsS

Salut,

Si je comprend bien, tu vérifies aussi les nombres pairs ?

C'est une obligation la méthode récursive ?
17/03/2016, 16h33
tyrtamos

Bonjour,

Le problème de la récursion avec Python, c'est qu'on est assez rapidement limité par la taille de la pile. Dans les cas "désespérés", on peut essayer de l'augmenter (sys.setrecursionlimit(...)), mais c'est un pis-aller.

Il existe bien des problèmes qui se résolvent de façon très élégante avec la récursion. Par exemple, le parcours dans un arbre. Mais ici pour le crible d’Ératosthène, une bonne boucle est largement suffisante.

Donc, à mon avis, et dans la mesure où il ne s'agit pas d'une étude portant sur la récursion, une bonne amélioration du code proposé est de supprimer la récursion... :D

Il existe par ailleurs de nombreuses astuces pour accélérer les calculs, et surtout pour supporter de monter très haut dans les nombres avant d'avoir des problèmes de mémoire.

Je me suis un peu amusé à ça il y a quelques temps, et, sans prétendre être au top, j'ai réussi à calculer les 455052511 nombres premiers inférieurs à 10 milliard en une heure environ. Il faut bien se rendre compte de ce que représentent une telle quantité de nombres: enregistrés sur disque, ils nécessitent un fichier de plus de 5 Go...
18/03/2016, 19h00
fifafou

N={x for x in range(1,n+1)} peut être remplacé par N=range(1,n+1)}
18/03/2016, 19h14
tyrtamos
Bonjour,

Sous Python 3, range est un itérateur. On peut donc obtenir la liste complète avec:
Code:

1 2 3 N=list(range(1,11)) print(N) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
18/03/2016, 19h27
wiztricks

La construction N={x for x in range(1,n+1)} fabrique un "set".
On peut le remplacer par set(range(1, n + 1)).
nota, mais pour savoir si c'est "mieux", il faut quand même mesurer.

- W
19/03/2016, 18h48
fifafou

Citation:

Envoyé par VinsS

Salut,
Si je comprend bien, tu vérifies aussi les nombres pairs ?

je pense aussi que les nombres pairs allant de deux en deux,il doit y avoir une moyen d'optimiser le code de ce coté là.
21/03/2016, 20h39
dividee

Au sujet de la récursion, dans le cas présent, je ne pense pas que ça apportera beaucoup de la supprimer.

La profondeur des appels récursifs ne croît que très lentement avec n. Si n = 10⁵¹² on n'aura que 9 ou 10 appels récursifs, mais il est bien sûr impossible d'aller jusque là avec un crible.

Idem au niveau du temps de calcul; même si on va recalculer plusieurs fois les premiers nombres premiers à cause de l'implémentation récursive, la quantité de "recalculs" est à peine supérieure à la racine carrée de n ce qui est négligeable (moins de 32000 pour n = 10⁹).

pyprimes contient quelques implémentations intéressantes de cribles, dont notamment une implémentation récursive assez élégante du crible d'Eratosthène (le générateur sieve() dans sieve.py)
22/03/2016, 03h36
elodouwen

Citation:

Envoyé par fifafou

N={x for x in range(1,n+1)} peut être remplacé par N=range(1,n+1)}

bonjour
pouvez vous préciser ?
voulez vous dire

Code:

N={range(1,n+1)}

?
chez moi ça ne marche pas
22/03/2016, 03h36
elodouwen

Citation:

Envoyé par VinsS

Salut,

Si je comprend bien, tu vérifies aussi les nombres pairs ?

C'est une obligation la méthode récursive ?

salut
c'est pour le plaisir la méthode récursive
je voualis juste voir si j'étais capable de faire ce truc des nombres premiers en méthode récursive
22/03/2016, 03h39
elodouwen
Citation:
Envoyé par tyrtamos

Bonjour,

Sous Python 3, range est un itérateur. On peut donc obtenir la liste complète avec:

Code:

1 2 3 N=list(range(1,11)) print(N) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
salut
dans mon programme tel que je l'ai imaginé, N doit être un set et non pas une list
car je sais faire set.remove mais je ne sais pas enlever un élément situé "en plein milieu" d'une liste

d'autre part je ne vois pas la différence entre

Code:

N=list(range(1,11))

et

Code:

N=range(1,11)

peux tu m'éclairer ?
22/03/2016, 03h40
elodouwen

Citation:

Envoyé par wiztricks

La construction N={x for x in range(1,n+1)} fabrique un "set".
On peut le remplacer par set(range(1, n + 1)).
nota, mais pour savoir si c'est "mieux", il faut quand même mesurer.

- W

ok merci de l'info
22/03/2016, 03h41
elodouwen

Citation:

Envoyé par dividee

pyprimes contient quelques implémentations intéressantes de cribles, dont notamment une implémentation récursive assez élégante du crible d'Eratosthène (le générateur sieve() dans sieve.py)

meric de l'info je vais regarder en détail de ce côté là
Vincent