Split your code into smaller, reusable, testable, documented parts
You could re-organise your code to make it clearer, easier to test and thus easier to improve by writing small functions with a clear purpose, with a proper return value (instead of relying on global variable).
import time
def get_primes(n):
"""Get list of prime number from 2 to n included."""
prime_list = []
numbers = set(range(n, 1, -1))
while numbers:
p = numbers.pop()
prime_list.append(p)
numbers.difference_update(set(range(p*2, n+1, p)))
return prime_list
def euler35(limit = 100000):
count = 0
prime_list = get_primes(limit)
for r in xrange(2,limit):
if r in prime_list:
num = str(r)
if (all(int(num[i:]+num[:i]) in prime_list for i in xrange(len(num)))):
count += 1
return count
def test_get_primes():
assert get_primes(1) == []
assert get_primes(2) == [2]
assert get_primes(7) == [2, 3, 5, 7]
assert get_primes(8) == [2, 3, 5, 7]
assert get_primes(9) == [2, 3, 5, 7]
assert get_primes(10) == [2, 3, 5, 7]
assert get_primes(11) == [2, 3, 5, 7, 11]
def test_euler35():
assert euler35(100) == 13
assert euler35() == 43
test_get_primes()
time.clock()
test_euler35()
print(time.clock())
Optimisation : using the right data structure for the right task
As mentionned in the other answer, using a set instead of a list should lead to clear performance improvements.
You just need to update :
prime_list = get_primes(limit)
into:
prime_set = set(get_primes(limit))
Simplify your code
You could get rid of if r in prime_set by iterating directly prime_set. Also you can get rid of superfluous parenthesis:
def euler35(limit = 100000):
count = 0
prime_set = set(get_primes(limit))
for r in prime_set:
num = str(r)
if all(int(num[i:]+num[:i]) in prime_set for i in xrange(len(num))):
count += 1
return count
Different prime generation algorithm
I am not quite sure how your prime generation algorithm is supposed to work but a simple implementation of the Eratosthenes algorithm proves to be slightly faster (at least on my machine).
This is the nice benefit of having split your code into small meaningful part is that you can easily change the underlying implementation.
def sieve(lim):
"""Computes the sieve of Eratosthenes for values up to lim included."""
primes = [True] * (lim + 1)
primes[0] = primes[1] = False
for i in range(2, int(math.sqrt(lim)) + 1):
if primes[i]:
for j in range(i * i, lim + 1, i):
primes[j] = False
return primes
def primes_up_to(lim):
"""Uses a sieve to return primes up to lim included."""
return (i for i, p in enumerate(sieve(lim)) if p)
def euler35(limit = 1000000):
count = 0
prime_set = set(primes_up_to(limit))
for r in prime_set:
num = str(r)
perms = [int(num[i:]+num[:i]) for i in xrange(len(num))]
if all(p in prime_set for p in perms):
count += 1
return count
Different strategy
Usually Project Euler is more than just implementing the straight forward solution : it could be a good idea to find a solution that would work for even bigger search spaces. You'll find such a strategy in this other code review.
Here is the code I had written (the argument works slightly differently but you'll get the spirit) and the corresponding unit tests you could use to check that my code runs ~10 times faster:
def is_prime(n):
"""Checks if a number is prime."""
if n < 2:
return False
return all(n % i for i in range(2, int(math.sqrt(n)) + 1))
def euler35_bis(nb_dig_max=6):
# permutations of 2 digits or more must contain only 1, 3, 7, 9
count = 4 # counting 2, 3, 5 and 7
final_numbers = {'1', '3', '7', '9'}
for l in range(2, nb_dig_max + 1):
for p in itertools.product(final_numbers, repeat=l):
p_int = int(''.join(p))
perm = {int(''.join(p[i:] + p[:i])) for i in range(len(p))}
if p_int == min(perm) and all(is_prime(n) for n in perm):
count += len(perm)
return count
def test_euler35():
assert euler35(100) == 13
assert euler35(100000) == 43
assert euler35() == 55
def test_euler35_bis():
assert euler35_bis(2) == 13
assert euler35_bis(5) == 43
assert euler35_bis() == 55
test_get_primes()
time.clock()
test_euler35()
# test_euler35_bis()
print(time.clock())
while numbers: p = numbers.pop() prime_list.append(p)that does not work. sets are not sorted. If it works, it is by chance. \$\endgroup\$