[Tutor] primes

[Kent Johnson]

Max Noel wrote:
> #!/usr/bin/env python
> 
> import math
> import timeit
> 
> def primeConcise(limit):
>     return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] 
> + range(3,x,2) if x%y==0]]
> 
> 
> def primeConciseOptimized(limit):
>     return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] 
> + range(3,int(math.sqrt(x)), 2) if x%y==0]]

Hmm, I didn't know that 9 and 15 were prime...
When I'm doing timings like this I usually check the output. You can write a *very* fast algorithm 
if correctness does not count :-)

Here is a version that gives correct results at least up to limit=50:

def primeConciseOptimized(limit):
     return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + 
range(3,int(math.sqrt(x))+1, 2) if x%y==0]]

One reason your listPrimes() function is faster is that it short-circuits the test - as soon as a 
divisor is found for a candidate, no further testing is done. primeConciseOptimized() always tests 
all the candidate divisors.

In the spirit of useless optimizations of bad algorithms ;) I used itertools to make a 
short-circuiting version of primeConciseOptimized():

import itertools
def no(seq, pred=bool):
     '''Returns True if pred(x) is False for every element in the iterable
        From the itertools recipes. '''
     for elem in itertools.ifilter(pred, seq):
         return False
     return True

def primeConciseOptimized2(limit):
     return [2] + [x for x in xrange(3, limit, 2) if no(xrange(3,int(math.sqrt(x))+1, 2), lambda y: 
x%y==0)]

Note I don't bother testing for divisibility by 2 since the candidates are all odd. This allows 
using xrange() instead of range() for a significant improvement.

My times:
listPrimes 0.143752069048
primeConciseOptimized 0.586845814203
primeConciseOptimized2 0.391731351331

Kent

> 
> def isPrime(x, primeList):
>     limit = int(math.sqrt(x))
>     for i in primeList:
>         if x % i == 0:
>             return False
>         if i >= limit:
>             break
>     return True
> 
> def listPrimes(upperLimit):
>     listOfPrimes = [2]
>     for i in xrange(3, upperLimit, 2):
>         if isPrime(i, listOfPrimes):
>             listOfPrimes.append(i)
>     return listOfPrimes
> 
> 
> if __name__ == '__main__':
>     t1 = timeit.Timer('listPrimes(50000)', 'from __main__ import 
> listPrimes')
>     t2 = timeit.Timer('primeConciseOptimized(50000)', 'from __main__ 
> import primeConciseOptimized')
>     t3 = timeit.Timer('primeConcise(50000)', 'from __main__ import 
> primeConcise')
>     print t1.timeit(1)
>     print t2.timeit(1)
>     print t3.timeit(1)
> 
> 
> 
> -- Max
> maxnoel_fr at yahoo dot fr -- ICQ #85274019
> "Look at you hacker... A pathetic creature of meat and bone, panting and 
> sweating as you run through my corridors... How can you challenge a 
> perfect, immortal machine?"
> 
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>