Python Implementation of Problem 35
View source code here on GitHub!
Includes
is_primes()
Problem Solution
Project Euler Problem 35
This ended up being a filtering problem. The problem with my solution is that I am not satisfied with my filter at all. I feel like there is a more efficient way to go about it.
Problem:
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?
1"""
2Project Euler Problem 35
3
4This ended up being a filtering problem. The problem with my solution is that I
5am not satisfied with my filter at all. I feel like there is a more efficient
6way to go about it.
7
8Problem:
9
10The number, 197, is called a circular prime because all rotations of the
11digits: 197, 971, and 719, are themselves prime.
12
13There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71,
1473, 79, and 97.
15
16How many circular primes are there below one million?
17"""
18from typing import Iterator
19
20from .lib.primes import is_prime
21
22
23def rotations(x: int) -> Iterator[int]:
24 r = repr(x)
25 for y in range(len(r)):
26 yield int(r[y:] + r[:y])
27
28
29def main() -> int:
30 answer = 0
31 for x in range(1000000):
32 if all(is_prime(r) for r in rotations(x)):
33 answer += 1
34 return answer