project_euler.problem_035.sol1

Project Euler Problem 35 https://projecteuler.net/problem=35

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.

Attributes

i
sieve

Functions

contains_an_even_digit(→ bool)	Return True if n contains an even digit.
find_circular_primes(→ list[int])	Return circular primes below limit.
is_prime(→ bool)	For 2 <= n <= 1000000, return True if n is prime.
solution(→ int)

Module Contents

project_euler.problem_035.sol1.contains_an_even_digit(n: int) → bool

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

project_euler.problem_035.sol1.find_circular_primes(limit: int = 1000000) → list[int]

Return circular primes below limit. >>> len(find_circular_primes(100)) 13 >>> len(find_circular_primes(1000000)) 55

project_euler.problem_035.sol1.is_prime(n: int) → bool

For 2 <= n <= 1000000, return True if n is prime. >>> is_prime(87) False >>> is_prime(23) True >>> is_prime(25363) False

project_euler.problem_035.sol1.solution() → int

>>> solution()
55

project_euler.problem_035.sol1.i = 2

project_euler.problem_035.sol1.sieve