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"] < 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 --> ms

print "Found %d in %r ms." % (ans, elapsed_time)
  • 1
    \$\begingroup\$ Go to the Project Euler forum for that problem, page 8, a post by Cthuloid on April 16th, 2014 has Python code that finds the solution in 0.2 sec. \$\endgroup\$
    – Jaime
    Commented May 8, 2014 at 1:12

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.