Project Euler Solution 35: Circular primes
Here we have Problem 35: Circular primes, which can be just solved without the insight. This made this problem especially fun.
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?
First we need to get a list of primes under one million. The prime generator is too slow, we need to take the prime sieve from Solution 7: 10001st prime.
Then we need something to generate all cycles of a number. We can implement this as a generator again.
def iter_cycles(n: int) -> Iterator[int]: digits = str(n) for _ in range(len(digits)): yield int(digits) digits = digits[1:] + digits[0]
Then we just go through all the primes, check all their cycles and if all cycles are primes, we count this number. It takes slighlty above 1 minute on my laptop, which is not fast enough. There is an insight that one has to have (which I didn't have at first): If there is an even digit or a 5 in the prime number, the cycle where this is the last digit cannot be a prime number. Therefore we can directly exclude all primes which have a 0, 2, 4, 5, 6 or 8 in them. This makes the program run much faster.
def solution() -> int: num_cyclic_primes = 0 primes = prime_sieve(1_000_000) for prime in primes: if set(str(prime)) & {"0", "2", "4", "5", "6", "8"}: continue for cycle in iter_cycles(prime): if cycle not in primes: break else: num_cyclic_primes += 1 return num_cyclic_primes
This finishes in 1.5 s, which is much more acceptable.