# [Tutor] primes

Kent Johnson kent37 at tds.net
Fri Mar 18 03:15:48 CET 2005

```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
>

```