[Tutor] primes

[Pierre Barbier de Reuille]

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

INRA - UMR Cirad/Inra/Cnrs/Univ.MontpellierII AMAP
Botanique et Bio-informatique de l'Architecture des Plantes
TA40/PSII, Boulevard de la Lironde
34398 MONTPELLIER CEDEX 5, France

tel   : (33) 4 67 61 65 77    fax   : (33) 4 67 61 56 68