[Tutor] Help Optimise Code

[Lie Ryan]

On Wed, 19 Nov 2008 13:13:18 +0000, Richard Lovely wrote:

> 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
>     # 'L' for unsigned long - not tested if 
>     # using a smaller type is faster
>     knownPrimes = array.array("L",(3,5)) 
>     for x in count2(7):
>         # take extra function calls out of the inner loop
>         sqrtX = sqrt(x) 
>         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
> 

Do you know that every prime number is in the form 6*x+1 or 6*x-1, except 
2 and 3. This means that instead of checking all odd numbers, you could 
loop over 6 numbers then yield n - 1 and n + 1.

def count6(start):
    while True:
        start += 6
        yield start - 1
        yield start + 1

And I've seen that you generated prime by dividing things up (actually 
modulus). Division and modulus is the slowest arithmetic operator, avoid 
it if you can. If you knows the upper bound beforehand, it is faster to 
use multiplication and an array of fixed size, i.e. "Sieve of 
Erasthotenes". If you intend to generate primes without known upper bound 
though, using sieve complexify things up.