Euler Problem 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?



In [1]:

    
N = 1000000
prime = [False, False] + [True] * (N - 2)
primes = []
for p in range(2, N):
    if prime[p]:
        primes.append(p)
        for q in range(p*p, N, p):
            prime[q] = False
count = 0
pow10 = 1
k_max = 1
for p in primes:
    k = len(str(p))
    if k > k_max:
        pow10 *= 10
        k_max = k
    for i in range(k-1):
        p = p//10 + (p%10) * pow10
        if not prime[p]:
            break
    else:
        count += 1
print(count)



In [ ]: