Project Euler Problem 37 in Python 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 &gt; 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 &gt; 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())
Use the right data structure for the job. If you have

            if int(n) not in primes:


called more than a small constant number of times then primes should not be a list. If you change


primes = [i for i in gen_primes(10000000)]



to

primes = set(i for i in gen_primes(10000000))


you will see a significant speedup.



The algorithm could also be improved. I don't want to go into too much detail here because that's not in keeping with the ethos of Project Euler, but I think I can give you a couple of hints:

The problem statement says that there are only eleven primes matching the criterion. What property of primes with the criterion allowed them to prove that? How can you apply that property to generate them faster?


   If you have found all of the truncatable primes of length n, do you need to loop over all truncations of a candidate number of length n+1?