3
\$\begingroup\$

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)
\$\endgroup\$
1
  • 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 May 8 '14 at 1:12
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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