# [Tutor] primes

Pierre Barbier de Reuille pierre.barbier at cirad.fr
Fri Mar 18 12:08:14 CET 2005

```Gregor Lingl a écrit :
> Hi!
> Who knows a more concise or equally concise but more efficient
> expression, which returns the same result as
>
> [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]
>
> Gregor
>
> P.S.: ... or a more beautiful one ;-)
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>

The fastest know way for your problem is the Eratosten sieve ...

Here's an implementation :

from sets import Set
from math import sqrt

def sieve( max ):
max_val = int( sqrt( max ) )
s = Set(xrange( 4, max, 2 ))
for i in xrange( 3, max_val, 2 ):
s.update( xrange( 2*i, max, i ) )
return [ i for i in xrange( 2, max ) if i not in s ]

I compared with the implementations of Gregor (optimized) and Max and
here is the result :

listPrimes(100000)            = 0.637619972229 (Max implementation)
primeConciseOptimized(100000) = 2.9141831398   (Gregor optimized)
sieve(100000)                 = 0.49525809288  (Eratosten sieve)

You'll just notice that Eratosten sieve is O(n) space consumption when
others are less (I don't remember the density of prime numbers :o) )
were n is the maximum number you're looking for.

Pierre

--
Pierre Barbier de Reuille