1
|
|
|
""" |
2
|
|
|
Project Euler Problem 35: Circular Primes |
3
|
|
|
========================================= |
4
|
|
|
|
5
|
|
|
.. module:: solutions.problem35 |
6
|
|
|
:synopsis: My solution to problem #35. |
7
|
|
|
|
8
|
|
|
The source code for this problem can be |
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem35.py>`_. |
10
|
|
|
|
11
|
|
|
Problem Statement |
12
|
|
|
################# |
13
|
|
|
|
14
|
|
|
The number, :math:`197`, is called a circular prime because all rotations of the digits: :math:`197, 971`, and |
|
|
|
|
15
|
|
|
:math:`719`, are themselves prime. |
16
|
|
|
|
17
|
|
|
There are thirteen such primes below :math:`100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79`, and :math:`97`. |
|
|
|
|
18
|
|
|
|
19
|
|
|
How many circular primes are there below one million? |
20
|
|
|
|
21
|
|
|
Solution Discussion |
22
|
|
|
################### |
23
|
|
|
|
24
|
|
|
Simply iterate over the primes below one million and count how many satisfy the conditions for a circular prime. |
|
|
|
|
25
|
|
|
|
26
|
|
|
Solution Implementation |
27
|
|
|
####################### |
28
|
|
|
|
29
|
|
|
.. literalinclude:: ../../solutions/problem35.py |
30
|
|
|
:language: python |
31
|
|
|
:lines: 34- |
32
|
|
|
""" |
33
|
|
|
|
34
|
|
|
from typing import Iterator |
35
|
|
|
|
36
|
|
|
from lib.digital import num_digits |
37
|
|
|
from lib.sequence import Primes |
38
|
|
|
|
39
|
|
|
|
40
|
|
|
def rotated(p: int) -> Iterator[int]: |
|
|
|
|
41
|
|
|
""" Generate all rotations of the decimal digits of `p` |
42
|
|
|
|
43
|
|
|
:param p: the initial value of `p` |
44
|
|
|
:return: a generator of all decimal digit rotations of `p` |
45
|
|
|
""" |
46
|
|
|
|
47
|
|
|
def rotl(x: int, n: int) -> int: |
|
|
|
|
48
|
|
|
""" Helper function to rotate the decimal digits of `x` left by one position |
49
|
|
|
|
50
|
|
|
:param x: the integer to rotate |
51
|
|
|
:param n: the number of decimal digits in `x` |
52
|
|
|
:return: x left rotated by one digit |
53
|
|
|
""" |
54
|
|
|
|
55
|
|
|
return ((x * 10) + int(x // (10 ** (n - 1)))) % (10 ** n) |
56
|
|
|
|
57
|
|
|
n_digits = num_digits(p, base=10) |
58
|
|
|
q = rotl(p, n_digits) |
|
|
|
|
59
|
|
|
while q != p: |
60
|
|
|
yield q |
61
|
|
|
q = rotl(q, n_digits) |
|
|
|
|
62
|
|
|
|
63
|
|
|
|
64
|
|
|
def solve(): |
65
|
|
|
""" Compute the answer to Project Euler's problem #35 """ |
66
|
|
|
|
67
|
|
|
upper_bound = 1000000 |
68
|
|
|
|
69
|
|
|
# Get all primes lower than one million, build a set to make membership tests cheap, i.e. O(1) |
70
|
|
|
primes = set(Primes(upper_bound=upper_bound)) |
71
|
|
|
|
72
|
|
|
# Iterate over the primes, checking for those that are circular |
73
|
|
|
answer = 0 |
74
|
|
|
for prime in primes: |
75
|
|
|
for q in rotated(prime): |
|
|
|
|
76
|
|
|
if q not in primes: |
77
|
|
|
break |
78
|
|
|
else: |
79
|
|
|
answer += 1 |
80
|
|
|
|
81
|
|
|
return answer |
82
|
|
|
|
83
|
|
|
|
84
|
|
|
expected_answer = 55 |
|
|
|
|
85
|
|
|
|
This check looks for lines that are too long. You can specify the maximum line length.