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

• 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. – TZHX Jun 8 '12 at 10:21
• getPrimes takes the most time (about 1.9s according to the python profiler). – cobie Jun 8 '12 at 10:23
• and I'm fairly sure you'll be having duplicates in the non_primes list. – TZHX Jun 8 '12 at 10:25
• 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 Jun 8 '12 at 10:27
• and I just don't think your method of determining circular primes is efficient. can't even work out it it's correct, tbh. – TZHX Jun 8 '12 at 10:30

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:
print(len(circular_primes))
print("Time (s)     : " + str(time.time()-start))

main()

• a bit of comments would help. – cobie Jun 8 '12 at 22:55

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