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 goin

StackExchange Code Review Q#58610, answer score: 14