Use a membership testing kit instead of an array. The hash search will be O (1) instead of O (n). This is the biggest bottleneck.
Exit the cycle as soon as you see that this is not a circular stroke, and not an attempt at other rotations. This is another bottleneck.
Here I have isolated roundness testing in a function that allows you to create a list with list comprehension. Having this in a function, let's return False as soon as we find out that it is not circular. Another alternative would be to do this in a for and break loop, when we know that it is not circular. Then add the else clause to the list in the loop. Generally speaking, comps is faster than adding in a loop. This may not be the case because it adds extra function calls. If you really care about speed, it would be useful to profile both options.
primes = set(primes_to_one_million_however_you_want_to_get_them) def is_circular(prime, primes=primes): prime_str = str(prime) # With thanks to Sven Marnach comments return all(int(prime_str[i:]+prime_str[:i]) in primes for i in xrange(len(prime_str))) circular_primes = [p for p in primes if is_circular(p)]
I also used the global value transfer trick as the default argument to the is_circular function. This means that it can be accessed inside the function as a local variable instead of a global variable that runs faster.
Here's one way to encode it using an else clause in a loop to get rid of this ugly flag and increase efficiency.
circular = [] for p in primes: prime_str = str(prime) for i in xrange(len(prime_str)): if int(prime_str[i:]+prime_str[:i]) not in primes: break else: circular.append(p)