Improving runtime of prime generation

Question

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 > 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 1

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()

Answer 2

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]])