Problem

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

Solution

**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)
```

“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.