Truncatable Primes -- Project Euler 37? I just finished Project Euler 37 after a bit of debugging and can't figure out how to make it faster. Whenever I add extra tests that I want to speed the program up, it ends up just slowing it down. My primes test is from here. Please help me optimize!

from primes import test as is_prime
from itertools import product
from timeit import default_timer as timer

def is_trunc(list_num):
    num = ''.join(map(str, list_num)) # turn (1, 2, 3) into 123
    if is_prime(int(num)):
        for k in range(1, len(num)):
            if not is_prime(int(num[k:])) or not is_prime(int(num[:k])):
                return False
        return True
    return False

start = timer()
data = {"count": 0, "length": 2, "sum": 0}

while data["count"] &lt; 11:
    for combo in product([1, 2, 3, 5, 7, 9], repeat = data["length"]):
        if is_trunc(combo):
            data["count"] += 1
            data["sum"] += int(''.join(map(str, list(combo))))
    data["length"] += 1

ans = data["sum"]
elapsed_time = (timer() - start) * 1000 # s --&gt; ms

print "Found %d in %r ms." % (ans, elapsed_time)
There's no need to convert lists to ints every time. Truncation from the right is an integer division by 10. Truncation from the left is modulo certain power of ten; you can keep track of the modulo as the loop progresses.

There's no need to run a very expensive primality every time. Keep track of the primes you already found.

PS: The biggest hint in the problem is that there's only 11 numbers of interest. There must be a way to prove that fact, and the proof is most likely constructive.