Project Euler 35: Circular primes below 1 million

Question

I'm doing another Project Euler problem, number 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?

import math  
num = 0  
primeList = []

def isprime(test):
    if test == 2:  
        primeList.append(2)  
        return True  
    elif test < 2:  
        return False  
    else:  
        for i in primeList:  
            if i > math.sqrt(test):
                break
            elif test % i == 0:
                return False
        primeList.append(test)
        return True

def rotations(n):
    answer = []
    rotation = n
    while not rotation in answer:
        answer.append(rotation)
        rotation = int(str(rotation)[1:] + str(rotation)[0])
    return answer

for i in range(2,1000000):
    numList = rotations(i)
    valid = True
    for j in numList:
        if not isprime(j):
            valid = False
    if valid:
        num += 1

    print(num)

I need help improving my code speed. What I really think is happening is the rotations() function is slowing the whole thing down.

Answer 1

Trial division repeatedly can get very expensive, and is not scalable in terms of computation time. Especially when you are running your rotation check during the process.

I would suggest getting a list together, then filtering that out. That way it is more efficient, and also when you rotate a number you just check if it is in the list, rather than rechecking it for primality slowly. Lookup tables are usually a good recommendation for these things, as the rotated elements overlap in spots. (such as 79 & 97, having to check if they are prime twice. It gets worse for longer numbers!)

To get all primes below 1,000,000 you can implement the Sieve of Eratosthenes to quickly get the list of primes.

from math import sqrt

def sieve(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False

    for x in range(4,n+1,2):
        primes[x] = False

    for x in range(3,int(sqrt(n))+1,2):
        if(primes[x]):
            for y in range(x*x,n+1,x):
                primes[y] = False

    return primes

Now you just go through the returned list, and for each True entry, you can check if it's rotatable.

And here is a simpler way to right a rotation. This one shifts left.

def rotate(n):
    n=str(n)
    return n[1:]+n[:1]

And with that rotation, and the sieve available to us, we now just rotate the number, and check if it is True in the sieve! Return false if any rotation of n is False, else return True if we can't find any non-primes.

def isRotatable(n, primes):
    for x in range(2,n):
        n = rotate(n)
        if not primes[int(n)]:
            return False
    return True

Now for a main method to just go through and print the results for us! I'm using main because I'm not sure what else to name it.

def main(n):
    primes = sieve(n)
    for x in range(2, len(primes)):
        if(isRotatable(x,primes)):
            print(x)

Altogether these pieces should work rather quickly. The longest part I found was it actually outputting to the interpreter, possibly writing to a file may be quicker.

Answer 2

Other people have pointed out algorithm optimisations. I reckon you'll get even faster results if you have a look at my answer to a pretty similar question.

Let's go for actual code review:

A bug in rotations

def rotations(n):
    answer = []
    rotation = n
    while not rotation in answer:
        answer.append(rotation)
        rotation = int(str(rotation)[1:] + str(rotation)[0])
    return answer

One can see that you have written something that looks like a smart enough solution that stops when similar rotations are found.

Writing a few tests, it looks like it works properly :

print(rotations(123))
print(rotations(1233))
print(rotations(1212))

However, there is a bug hidden in the fact that you lose some information converting from int to string back and forth.

Consider the following examples :

print(rotations(10))
print(rotations(100))
print(rotations(1000))

Removing the conversions, you'd get :

def rotations(n):
    answer = []
    rotation = str(n)
    while not rotation in answer:
        answer.append(rotation)
        rotation = rotation[1:] + rotation[0]
    return answer

Not that it does not really change anything for the final result because impacted numbers contain a 0 and at least one rotation is not prime.

Code organisation

Try to put your code actually doing things behind an if __name__ == '__main__': guard.

Your function isprime does a lot more than its name suggests.

Try to write small simple methods doing one things so that you can easily test them.

Answer 3

Optimisation:

• Since primes can be represented as 6x+1 or 6x-1, you could run the loop by following a simple algorithm <LINK>.

  1. Add 2,3 as circular primes initially.
  2. Start with ias 5 a representation of (6x-1).
  3. Run the loop as currently done.
  4. Inside the loop check for i(6x-1) and i+2(6x+1) and after the loop increase iby 4.

  5. Rest follows the current algorithm.

     for i in range(2,1000000): // With above alogrithm it would be 3 times faster.

• numlist is calculated every time for 197, 971, 719. Instead if your isPrimes instead represented 3 values : IS_PRIME, IS_NOT_PRIME, IS_CIRCULAR_PRIME. So you would not have to rotate once you have already checked it before. As JPMC suggested, its best to have the primes calculated first

• Move this out of the loop and store it in a temp variable.

  if i > math.sqrt(test):