[Tutor] Help Optimise Code

[Richard Lovely]

I'm pretty new to code optimisation, so I thought I'd ask you all for advice.

I'm making an iterative prime number generator. This is what I've got so far:

Code: Select all
import math, array

def count2(start_at=0):
    'Yield every third integer, beginning with start_at'
    # this has been tested as faster than using itertools.count
    while True:
        yield start_at
        start_at += 2

def iprimes():
    'generate an endless sequence of prime numbers'
    yield 2
    yield 3
    yield 5
    sqrt = math.sqrt
    knownPrimes = array.array("L",(3,5)) # 'L' for unsigned long - not
tested if using a smaller type is faster
    for x in count2(7):
        sqrtX = sqrt(x) # take extra function calls out of the inner loop
        for p in knownPrimes):
            test = (not x % p) and -1 or p > sqrtX
            if test == -1: # (not x % p) == true
                break
            elif test: # (p > sqrtX) == true
                yield x
                knownPrimes.append(x)
                break


I've tried a the sieve of erath-whatever as in test_generator,
implemented using itertools functions, but it hit max recusion depth
somewhere before 1000 primes, and I'm after millions of primes.

I'm not particularly bothered about startup overheads, just the loops.

Quick thought: would the following work (I'm on a public computer
without python, so can't test):

Code: Select all
def iprimes():
    'generate an endless sequence of prime numbers'
    yield 2
    yield 3
    yield 5
    sqrt = math.sqrt
    knownPrimes = array.array("L",(3,5)) # 'L' for unsigned long - not
tested if using a smaller type is faster
    for x in count2(7):
        sqrtX = sqrt(x) # take extra function calls out of the inner loop
        for test in ((not x % p) and -1 or p > sqrtX for p in
knownPrimes)): # a generator _should_ be faster...
            if test == -1: # (not x % p) == true
                break
            elif test: # (p > sqrtX) == true
                yield x
                knownPrimes.append(x)
                break


Please don't suggest changing languages. I like python. Although if
you want to write an extension for me, and provide the source and a
makefile, please feel free. I have a MinGW install that's doing
nothing.  (Just kidding - almost.)

This is NOT homework.

-- 
Richard "Roadie Rich" Lovely, part of the JNP|UK Famile
www.theJNP.com