Improving runtime of prime generation I just answered the question on project euler about finding circular primes below 1 million using python. My solution is below. I was able to reduce the running time of the solution from 9 seconds to about 3 seconds. I would like to see what else can be done to the code to reduce its running time further. This is strictly for educational purposes and for fun.

import math
import time

def getPrimes(n):
    """returns set of all primes below n"""
    non_primes = [j for j in range(4, n, 2)] # 2 covers all even numbers
    for i in range(3, n, 2):
        non_primes.extend([j for j in range(i*2, n, i)])
    return set([i for i in range(2, n)]) - set(non_primes)


def getCircularPrimes(n):
    primes = getPrimes(n)
    is_circ = []
    for prime in primes:

        prime_str = str(prime)
        iter_count = len(prime_str) - 1

        rotated_num = []
        while iter_count &gt; 0:
            prime_str = prime_str[1:] + prime_str[:1]
            rotated_num.append(int(prime_str))
            iter_count -= 1

        if primes &gt;= set(rotated_num):
            is_circ.append(prime)

    return len(is_circ)
Python 2.7: 100 ms, pypy 1.8.0: 60 ms (Intel Core i7-3770K, 4x 3.50GHz):

import time

def rwh_primes2(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n&gt;=6, Returns a list of primes, 2 &lt;= p &lt; n """
    correction = (n%6&gt;1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
        sieve[(k*k+4*k-2*k*(i&amp;1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&amp;1))/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

def main():
    start = time.time()
    primes = set(rwh_primes2(1000000))
    circular_primes = set()
    for prime in primes:
        include = True  
        s = str(prime)
        for n in xrange(len(s)-1):  
          s = s[1:] + s[:1]
          if int(s) not in primes: 
              include = False
              break 
        if include:     
            circular_primes.add(prime)
    print(len(circular_primes))
    print("Time (s)     : " + str(time.time()-start))

main()