Python premier générateur dans une ligne

ce n'est pas le Crible d'Eratosthène, même si on dirait qu'il est. Il est en fait bien pire. Le tamis est le meilleur algorithme pour trouver des nombres premiers.

voir http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

edit : j'ai modifié https://stackoverflow.com/a/9302299/711085 pour être une doublure (à l'origine ce N'était pas le vrai tamis, mais maintenant il l'est... probablement...):

reduce( (lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r), 
        range(2,N), set(range(2,N)))

Démo:

>>> primesUpTo(N): lambda N: reduce(...)
>>> primesUpTo(30)
{2, 3, 5, 7, 11, 13, 17, 19}

---

malheureusement, je pense que bien que ce serait efficace dans un langage de programmation fonctionnel, il pourrait ne pas être aussi efficace en python en raison de non-persistance (état partagé et immuable) des structures de données, et tout tamis en python aurait besoin d'utiliser la mutation pour atteindre des performances comparables. On peut encore le mettre dans une doublure si on le veut désespérément. Mais d'abord...

tamis Normal:

>>> N = 100
>>> table = list(range(N))
>>> for i in range(2,int(N**0.5)+1):
...     if table[i]:
...         for mult in range(i**2,N,i):
...             table[mult] = False
... 
>>> primes = [p for p in table if p][1:]
>>> primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

nous pouvons maintenant définir et appeler des fonctions anonymes sur la même ligne, ainsi que le hack de [...].__setitem__ pour faire la mutation en ligne, et le hack de ... and foo pour évaluer ... tout en retournant foo :

>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N)))
>>> primesUpTo(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Procéder à grincer des dents dans l'horreur, le one-liner élargi (bizarrement belle parce que vous pourrait presque traduire directement les flux de contrôle, mais un terrible abus de tout):

lambda N:
    (lambda table: 
        [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] 
            for i in range(2,int(N**0.5)+1) if table[i]] 
        and [p for p in table if p][1:]
    )(list(range(N)))

cette version mutante à une doublure a abandonné à environ 10 ⁸ sur ma machine, tandis que la version mutante originale a abandonné à environ 10 ⁹ , s'épuisant de mémoire (curieusement).

L'original reduce version a donné jusqu'à 10 ⁷ . Alors peut-être ce n'est pas que inefficace après tout (au moins pour les nombres que vous pouvez traiter avec sur votre ordinateur).

edit2 Il semble que vous pouvez les abus effets secondaires de façon plus concise:

reduce( (lambda r,x: (r.difference_update(range(x**2,N,x)) or r)
                     if (x in r) else r), 
        range(2,N), set(range(2,N)))

, Elle donne l'ordre de 10 ⁸ , de même que le one-liner mutation version.

edit3: Ce pistes O(N) empiriques de la complexité , alors que sans l' difference_update , il a couru à O(n^2.2) de la complexité .

limitation de la portée qui est réduite au-delà, à la rqrt de la limite supérieure, et de travail avec des cotes seulement , les deux donnent lieu à des vitesses supplémentaires ( 2x et 1,6 x correspondant):

reduce( (lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
                     if (x in r) else r), 
        range(3, int((N+1)**0.5+1), 2),
        set([2] + range(3,N,2)))