Efficiency of Project Euler problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

I have written the following program in python and am new to programming in Python. I am looking for suggestions for making efficient programs and developing good programming habits.

import math
data ={}

def isPrime(n):
global data
if n in data:
return data[n]

for num in range(2,math.floor(math.sqrt(n)+1)):
if n%num == 0:
data[n]=False
return False
data[n]=True
return True
count =0
data ={}

for num in range (2,1000000):
q=False
num=str(num)
for i in range(len(num)):
if (isPrime(int(num[i:]+num[:i]))):
q=True
else:
q=False
break
if q:
count+=1
print (count)


Style

In Python, there is usual style guide called PEP8 : I think you should follow it to make your code more consistent with all the Python code out in the wild out there. If you want to, you'll find various tools to help you check your Python code : pep8, pycheck, pylint, pyflakes.

Global variables

The fact that you are using a global variable is a good hint that your are probably doing something wrong. It makes your code harder to track but also harder to test and to benchmark.

Also, your should be moving your code which actually performs computations behing an if __name__ == "__main__": : this allows one to easily find where stuff are triggered in your code but also and more importantly to be able to re-use your code by importing your project without re-launching all the computations you might not care about while solving a different project euler problem.

At this point, your code looks like :

import math

def is_prime(n, dict_primes):
if n in dict_primes:
return dict_primes[n]

for num in range(2, math.floor(math.sqrt(n)+1)):
if n % num == 0:
dict_primes[n] = False
return False
dict_primes[n] = True
return True

def main():
"""Main function"""
print("Hello, world!")
count = 0
dict_primes = {}

for num in range (2, 1000000):
q = False
num = str(num)
for i in range(len(num)):
if is_prime(int(num[i:]+num[:i]), dict_primes):
q = True
else:
q = False
break
if q:
count += 1
print (count)

if __name__ == "__main__":
main()


Optimisations : different algorithm

You are using some kind of cache to remember the different numbers you've checked and this is a good idea. Also, you are using a quite efficient way to check if a single number is prime, stopping at sqrt(n) + 1. However, the best way to do this would probably be to implement a Sieve of Eratosthenes : we build it once and for all and we don't need to compute things later on. This is especially convenient here because we know that we will not need to check for any number bigger than one million.

This is already much faster :

import math

def sieve(limit):
primes = [True] * limit
primes[0] = primes[1] = False
for i in range(2, math.floor(math.sqrt(limit))):
if primes[i]:
for j in range(i*i, limit, i):
primes[j] = False
return primes

def main():
"""Main function"""
print("Hello, world!")
limit = 1000000
count = 0

primes = sieve(limit)
for num in range (2, limit):
q = False
num = str(num)
for i in range(len(num)):
if primes[int(num[i:]+num[:i])]:
q = True
else:
q = False
break
if q:
count += 1
print (count)

if __name__ == "__main__":
main()


Details

At the moment, you are using q to store whether all permutations of num where prime numbers so far. It might be interesting to point out that in Python, you can add an else to loops signifying that that was no break in the loop. Thus, you could write something like :

    for i in range(len(num)):
if not primes[int(num[i:]+num[:i])]:
break
else:
count += 1


Alternatively, you could use the all function to write it in a clean and concise way :

    if all(primes[int(num[i:]+num[:i])] for i in range(len(num))):
count += 1


Another optimisation

I haven't checked that this really makes the code faster but let's assume that 193939 and all its permutations are prime. Instead of checking all permutations for each permuation and adding one each time every thing is fine, we could only check that we are considering the smallest permutation and add the number of permutations directly. This would look like :

   perm = {int(num_s[i:]+num_s[:i]) for i in range(len(num_s))}
if all(n >= num and primes[n] for n in perm):
count += len(perm)


(Please note that I have used a set as I don't want 11 for instance to be counted multiple times just because it is its own permutation).

Another optimisation

If all permutations are supposed to be primes : we know that the first itself must be prime : we can get rid of even numbers : for num in range(3, limit, 2): (you have to initialise count with 1 to count 2).

Also, we know that no even numbers must be in the string : you can add : odd_numbers = {1, 3, 5, 7, 9} out of the loops and if {int(n) for n in num_s}.issubset(odd_numbers): in the loop.

Similarly, 5 can be excluded from the list of allowed numbers as anything ending with 5 with be a multiple of 5 : you can change odd_numbers for final_numbers = {1, 3, 7, 9} and start counting from 2.

Again, this is not benchmarked but you can give it a try if you want.

And now for something different

Instead of going through all numbers and checking conditions that will most of the time not be true, you can use the fact that you already know that for numbers bigger than 9, only {1, 3, 7, 9} are allowed. Thus, you could try to go through the carthesian product of theses numbers using itertool.product.

When considering numbers with n digits, you'll only consider 4**n numbers instead of 10**n (when n = 6 for instance, it makes the difference between 4096 and 100000).

Once this is done, you can even afford to check for much bigger numbers :

def main():
"""Main function"""
print("Hello, world!")
count = 4
nb_digits = 8
primes = sieve(10**nb_digits)
final_numbers = {'1', '3', '7', '9'}
for l in range(2, nb_digits+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(primes[n] for n in perm):
print(p, len(perm))
count += len(perm)
print (count)


This code checks for numbers of 8 digits by doing 13939 prime checks. Thus, it is not worth using the Eratosthene sieves anymore.

Using your initial code with no cache, we can achieve great performances :

def is_prime(n):
for num in range(2,math.floor(math.sqrt(n)+1)):
if n%num == 0:
return False
return True

def main():
"""Main function"""
print("Hello, world!")
count = 4
nb_digits = 9
final_numbers = {'1', '3', '7', '9'}
for l in range(2, nb_digits+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):
print(p, len(perm))
count += len(perm)
print (count)

• The is_prime in the final test can still be optimised quite easily. It's not necessary to consider all numbers from 2 to sqrt(n): at the very least you can add a wheel of length 6 to only do a third of the divisibility tests. May 11, 2016 at 11:36
• Using l as a variable here is really confusing, as it looks a ton like 1. (I had to read through this several times to catch it). Oct 6, 2017 at 5:05
• @OscarSmith Using len as variable name is also confusing and potentially dangerous. You are shadowing the built-in function len. Better call it the more descriptive length. Oct 6, 2017 at 7:51

"Memoization" (storing the previous results of function calls) is often done using a decorator in Python, rather than building it into the function itself:

def memoize(f):
"""Cache the results of calls to f."""
def func(*args):
if args not in func.cache:
func.cache[args] = f(*args)
return func.cache[args]
func.cache = {}
return func

@memoize
def is_prime(n): # note PEP-8 name
...


This makes your inner function easier to read and write, as it abstracts out the code needed to store previous call results. It also removes the global variable data, without adding an extra function parameter.

Let's just focus on your main loop:

for num in range (2,1000000):
q=False
num=str(num)
for i in range(len(num)):
if (isPrime(int(num[i:]+num[:i]))):
q=True
else:
q=False
break
if q:
count+=1
print (count)


q = True, q = False; break, if q: count += 1 look ugly. The name q is cryptic — what does it mean? What you really want is an is_circular_prime(n) function…

def is_circular_prime(n):
num = str(n)
for i in range(len(num)):
if not is_prime(int(num[i:] + num[:i])):
return False
return True


so that you can write

print(sum(1 for n in range(2, 1000000) if is_circular_prime(n)))


It's also beneficial to have an is_circular_prime() function so that you can verify that your implementation indeed reports that 197, 971, and 719 are all circular primes as claimed in the problem.