Re: [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@python.org
http://mail.python.org/mailman/listinfo/tutor
_______________________________________________
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor