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) 

• TZHX: do you have any idea which region takes the most time? the getPrimes method looks like it's going to be expensive, as you're building two very large sets then subtracting one from the other.
• cobie: getPrimes takes the most time (about 1.9s according to the python profiler).
• TZHX: and I'm fairly sure you'll be having duplicates in the non_primes list.
• TZHX: if getPrimes takes 1.9s, the rest of the function is taking 7.1. if you're using a profiler it's running in debug I assume? how does it perform in release?
• TZHX: and I just don't think your method of determining circular primes is efficient. can't even work out it it's correct, tbh.

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

• cobie: a bit of comments would help.

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