|
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
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.