Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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. 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)           
share|improve this question

3 Answers 3

up vote 5 down vote accepted

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 1000000).

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)
share|improve this answer
    
Thanks a lot , your observations are really helpful to me. –  yask Jul 31 at 12:46

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.