Euler Solution 60

From ProgSoc Wiki

Jump to: navigation, search

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Solutions

Python by Althalus

Runtime: 36.3 seconds

My 80th solution.

from primeFunctions import genPrimes
from time import time
start = time()

p2 = {}
# List of primes for comparing concatinations.
# Lookups in dictionaries are far faster than finding in a list.
primes = genPrimes(100000000) # same old function (utilises psyco)
while primes: # cant hold the list and the dict at same time.
    x = primes.pop()
    p2[str(x)] = 1 
    del x
primes = [str(x) for x in genPrimes(9999)] #smaller list to iterate over to build the concatinations from.

for i in range (0,len(primes)):
    for j in range (i+1,len(primes)):
        try: # If a key doesn't exist, it's not prime, so we can move on.
             p2[primes[j]+primes[i]]
             p2[primes[i]+primes[j]]
        except KeyError:
            continue
        for k in range (j+1,len(primes)):
            try:
                 p2[primes[k]+primes[i]]
                 p2[primes[i]+primes[k]]
                 p2[primes[k]+primes[j]]
                 p2[primes[j]+primes[k]]
            except KeyError:
                continue
            for l in range (k+1,len(primes)):
                try:
                     p2[primes[l]+primes[i]]
                     p2[primes[i]+primes[l]]
                     p2[primes[l]+primes[j]]
                     p2[primes[j]+primes[l]]
                     p2[primes[l]+primes[k]]
                     p2[primes[k]+primes[l]]
                except KeyError:
                    continue
                for m in range (l+1,len(primes)):
                    try:
                         p2[primes[m]+primes[i]]
                         p2[primes[i]+primes[m]]
                         p2[primes[m]+primes[j]]
                         p2[primes[j]+primes[m]]
                         p2[primes[m]+primes[k]]
                         p2[primes[k]+primes[m]]
                         p2[primes[m]+primes[l]]
                         p2[primes[l]+primes[m]]
                    except KeyError:
                        continue
                    print primes[i],primes[j],primes[k],primes[l],primes[m]
                    print sum([int(primes[i]),int(primes[j]),int(primes[k]),int(primes[l]),int(primes[m])])
                    print time()-start
                    exit()
Personal tools