Remarkable results with psyco and sieve of Eratosthenes

[dickinsm at gmail.com]

> BTW, can this code be made any more efficient?

I'm not sure, but the following code takes around 6 seconds on my
1.2Ghz iBook. How does it run on your machine?

def smallPrimes(n):
    """Given an integer n, compute a list of the primes < n"""

    if n <= 2:
        return []

    sieve = range(3, n, 2)
    top = len(sieve)
    for si in sieve:
        if si:
            bottom = (si*si - 3)//2
            if bottom >= top:
                break
            sieve[bottom::si] = [0] * -((bottom-top)//si)

    return [2]+filter(None, sieve)

smallPrimes(10**7)




>
> ============
>
> #!/usr/bin/python -OO
> import math
> import sys
> import psyco
>
> psyco.full()
>
> def primes():
>     primes=[3]
>     for x in xrange(5,10000000,2):
>         maxfact = int(math.sqrt(x))
>         flag=True
>         for y in primes:
>             if y > maxfact:
>                 break
>             if x%y == 0:
>                 flag=False
>                 break
>         if flag == True:
>             primes.append(x)
> primes()