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.