-
Notifications
You must be signed in to change notification settings - Fork 0
/
Problem037.py
38 lines (24 loc) · 1.15 KB
/
Problem037.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
"""
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
"""
from time import time
from math import log10
def prime_generator(N=10):
sieve = [False, False] + [True] * N # Added 0 and 1
for i in range(2, N+1):
if sieve[i]:
for j in range(i*i, N, i):
sieve[j] = False
return {i for i, is_prime in enumerate(sieve) if is_prime}
def is_truncable(x):
right = [x//10**i for i in range(1, int(log10(x) + 1))]
left = [x % 10**(i+1) for i in range(int(log10(x)))]
return all([i in lookup_prime for i in right+left])
lookup_prime = prime_generator(1_000_000)
start_time = time()
result = [i for i in lookup_prime if log10(i) > 1 and str(
i)[-1] in ("37") and str(i)[0] in ("2357") and is_truncable(i)]
final_time = time()
print(sum(result))