# time a function using time.time() and the @ function decorator
# uses Psyco to speed up code (on my computer 1.6 sec with Psyco, 4.4 sec without)
# download psyco-1.4.win32-py2.4.exe from
# http://psyco.sourceforge.net/
# tested with Python24    vegaseat    22aug2005
 
import time
from psyco import full
 
full()
 
def print_timing(func):
    def wrapper(*arg):
        t1 = time.time()
        res = func(*arg)
        t2 = time.time()
        print '%s took %0.3f ms' % (func.func_name, (t2-t1)*1000.0)
        return res
    return wrapper
 
# declare the @ decorator just before the function, invokes print_timing()
@print_timing
def getPrimeList(n):
    """ returns a list of prime numbers from 2 to < n using a sieve algorithm"""
    if n < 2:  return []
    if n == 2: return [2]
    # do only odd numbers starting at 3
    s = range(3, n+1, 2)
    # n**0.5 is slightly faster than math.sqrt(n)
    mroot = n ** 0.5
    half = len(s)
    i = 0
    m = 3
    while m <= mroot:
        if s[i]:
            j = (m*m-3)//2
            s[j] = 0
            while j < half:
                s[j] = 0
                j += m
        i = i+1
        m = 2*i+3
    return [2]+[x for x in s if x]
 
if __name__ == "__main__":
    print "prime numbers from 2 to <10,000,000 using a sieve algorithm"
    print "(speed improved with the psyco module)"
    primeList = getPrimeList(10000000)
    time.sleep(2.5)
 
"""
my output -->
prime numbers from 2 to <10,000,000 using a sieve algorithm
(speed improved with the psyco module)
getPrimeList took 1650.000 ms
"""