Project Euler 35: Circular primes below 1 million

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

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.

StackExchange Code Review Q#78370, answer score: 2