There is always room for optimizing primelist functions. Here is an assortment timed with Python module timeit …
'''primelist_timing1.py timing some very fast primelist functions tested with Python27 and Python32 by vegaseat ''' import timeit import numpy import sys print("Python version:\n %s\n" % sys.version) def time_function(stmt, setup): """ use module timeit to time functions """ # to enable garbage collection start setup with 'gc.enable();' #setup = 'gc.enable();' + setup t = timeit.Timer(stmt, setup) times = 10000 num = 100 # times*num has to be 1000000 to get time in microseconds/pass # (lower num is a little less precise but saves time) elapsed = (times * t.timeit(number=num)) print("%-20s --> %0.2f microseconds/pass" % (stmt, elapsed)) def primelist_bw(n): """ returns a list of primes < n by Bill Woods """ sieve = [True] * (n>>1) for x in range(3, int(n**0.5)+1, 2): if sieve[x>>1]: sieve[x*x//2::x] = [False] * ((n-x*x-1)//(x<<1)+1) return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]] def primelist_ds(n): """ returns a list of primes < n """ sieve = [True] * (n>>1) for x in range(3, int(n**0.5)+1, 2): if sieve[x>>1]: sieve[(x*x)>>1::x] = [False] * ((n-x*x-1)//(x<<1)+1) return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]] def primes_numpy(n): """ requires module numpy and n>=6, returns a list of primes 2 <= p < n """ sieve = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool) sieve[0] = False for x in range(int(n**0.5)//3+1): if sieve[x]: k = 3*x + 1|1 sieve[((k*k)//3)::2*k] = False sieve[(k*k+4*k-2*k*(x&1))//3::2*k] = False return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0]+1)|1)].tolist() # time a function stmt = 'primelist_bw(1000000)' setup = 'from __main__ import primelist_bw' time_function(stmt, setup) # time a function stmt = 'primelist_ds(1000000)' setup = 'from __main__ import primelist_ds' time_function(stmt, setup) # time a function stmt = 'primes_numpy(1000000)' setup = 'from __main__ import primes_numpy, numpy' time_function(stmt, setup) print('-'*60) # additional test (show the last 5 primes) ... print(primelist_bw(1000000)[-5:]) print(primelist_ds(1000000)[-5:]) print(primes_numpy(1000000)[-5:]) '''result ... Python version: 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)] primelist_bw(1000000) --> 75969.22 microseconds/pass primelist_ds(1000000) --> 73669.90 microseconds/pass primes_numpy(1000000) --> 9016.74 microseconds/pass ------------------------------------------------------------ [999953, 999959, 999961, 999979, 999983] [999953, 999959, 999961, 999979, 999983] [999953, 999959, 999961, 999979, 999983] Python version: 3.2.3 (default, Apr 11 2012, 07:15:24) [MSC v.1500 32 bit (Intel)] primelist_bw(1000000) --> 77284.28 microseconds/pass primelist_ds(1000000) --> 75547.38 microseconds/pass primes_numpy(1000000) --> 28055.11 microseconds/pass ------------------------------------------------------------ [999953, 999959, 999961, 999979, 999983] [999953, 999959, 999961, 999979, 999983] [999953, 999959, 999961, 999979, 999983] '''