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?


In [1]:
def prime_factors(n): # from eratosthenes
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        
        d = d + 1
        if d * d > n:
            if n > 1:
                factors.append(n)
            break
            
    return factors

def primes_less_than_n(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

max_num_digits = 6
all_primes = primes_less_than_n((10**max_num_digits+1)-1)
max_p = all_primes[-1]
all_primes = set(all_primes)
print len(all_primes)

def is_prime(n):
    if n <= max_p:
        return n in all_primes
    
    return len(prime_factors(n)) == 1


78498

In [2]:
import itertools

def rotations(a):
    l = list(a)
    for i in range(len(l)):
        l.insert(0, l[-1])
        del l[-1]
        
        yield ''.join(l)
    
circular_primes = []
for n in all_primes:
    d = str(n)
    is_circular = True
    for o in rotations(d):
        n2 = ''.join(list(o))
        if not is_prime(int(n2)):
            is_circular = False
            break
            
    if is_circular:
        circular_primes.append(n)

In [3]:
print len(circular_primes)
print circular_primes


55
[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 393919, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 939193, 331999, 919393, 37199, 39119, 319993, 193939, 199933, 71993, 91193, 93719, 93911, 999331, 99371, 933199, 939391, 391939, 993319]

In [ ]: