Question: I just answered the question on project euler about finding [circular primes below 1 million](http://projecteuler.net/problem=35) 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 > 0:
            prime_str = prime_str[1:] + prime_str[:1]
            rotated_num.append(int(prime_str))
            iter_count -= 1

        if primes >= set(rotated_num):
            is_circ.append(prime)

    return len(is_circ) 

```

Answer: 
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>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>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&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&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()

```
After a bit of fiddling coupled with some insight from SO on the topic which happens to be one with a lot of previous questions and answers, I was able to modify and get the running time of the getPrimes function down to 0.95s from 1.9s for an n value of 1000000. The code is given below and this was acheived by eliminating redundant instructions. Any more fiddling around is welcome.

```
def getPrimes(n):
    """returns set of all primes below n"""
    primes = [1] * n
    for i in range(3, n, 2):
        for j in range(i*3, n, 2*i):
            primes[j] = 0
    return len([1] + [primes[j] for j in range(3, n, 2) if primes[j]])

```