Project Euler Problem 37 asks:
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.
My approach can generate first 8 numbers "fairly" quickly and it relies on pregenerated list of primes created using sieve of eratosthenes. I've tried with active prime generation but it was slower, any way to optimize this code ?
from algorithms import *
primes = [i for i in gen_primes(10000000)]
def is_truncatable_right(n):
a = True
if n > 10:
for x in range(len(str(n))):
if int(n) not in primes:
a = False
n = str(n)[:-1]
return a
else:
return False
def is_truncatable_left(n):
a = True
if n > 10:
for x in range(len(str(n))):
if int(n) not in primes:
a = False
n = str(n)[1:]
return a
else:
return False
def main():
n = []
a = 11
while len(n) != 11:
if is_truncatable_left(a) and is_truncatable_right(a):
n.append(a)
a += 1
return n, sum(n)
print(main())