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?
The key to this problem is to reduce search space.
Also, if a number is not circular prime, then all of its circular numbers could not be circular prime. This could avoid twice-calculation.
import math
def could_be_circular_prime(n):
digits = list(map(int, str(n)))
digit_number = len(digits)
if any(map(lambda d: d % 2 == 0, digits)):
return False
elif 5 in digits:
return False
elif sum(digits) % 3 == 0:
return False
return True
def circular(n):
circulars = []
digit_number = len(str(n))
power = pow(10, digit_number-1)
for _ in range(digit_number):
circulars.append(n)
n = (n % 10) * power + n // 10
return set(circulars)
def is_prime(n):
if (n % 2 == 0 and n > 2) or n < 2:
return False
return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))
def solve(bound):
circular_primes = set([2, 3, 5])
candidates = set(filter(could_be_circular_prime, range(2, int(bound))))
while candidates:
c = candidates.pop()
circulars = circular(c)
if all(map(is_prime, circulars)):
circular_primes |= circulars
candidates -= circulars
return len(circular_primes), circular_primes
solve(100)
solve(1e6)