project euler problem 35 https projecteuler netproblem35 problem statement 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 to solve this problem in an efficient manner we will first mark all the primes below 1 million using the sieve of eratosthenes then out of all these primes we will rule out the numbers which contain an even digit after this we will generate each circular combination of the number and check if all are prime for 2 n 1000000 return true if n is prime isprime87 false isprime23 true isprime25363 false return true if n contains an even digit containsanevendigit0 true containsanevendigit975317933 false containsanevendigit245679 true return circular primes below limit lenfindcircularprimes100 13 lenfindcircularprimes1000000 55 solution 55 for 2 n 1000000 return true if n is prime is_prime 87 false is_prime 23 true is_prime 25363 false return true if n contains an even digit contains_an_even_digit 0 true contains_an_even_digit 975317933 false contains_an_even_digit 245679 true return circular primes below limit len find_circular_primes 100 13 len find_circular_primes 1000000 55 result already includes the number 2 solution 55
from __future__ import annotations

sieve = [True] * 1000001
i = 2
while i * i <= 1000000:
    if sieve[i]:
        for j in range(i * i, 1000001, i):
            sieve[j] = False
    i += 1


def is_prime(n: int) -> bool:
    
    return sieve[n]


def contains_an_even_digit(n: int) -> bool:
    
    return any(digit in "02468" for digit in str(n))


def find_circular_primes(limit: int = 1000000) -> list[int]:
    
    result = [2]  
    for num in range(3, limit + 1, 2):
        if is_prime(num) and not contains_an_even_digit(num):
            str_num = str(num)
            list_nums = [int(str_num[j:] + str_num[:j]) for j in range(len(str_num))]
            if all(is_prime(i) for i in list_nums):
                result.append(num)
    return result


def solution() -> int:
    
    return len(find_circular_primes())


if __name__ == "__main__":
    print(f"{len(find_circular_primes()) = }")