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
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
In [ ]: