# Project Euler #60 Prime pair sets

The problem is as below:

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

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

%%time
import itertools
import time

t1 = time.time()

def prime():

yield 3
yield 7

for i in itertools.count(11, 2):
e = int(i ** .5) + 1
for j in range(2, e + 1):
if i % j == 0:
break
else:
yield i

def is_prime(n):
if n < 2:
return False
if n == 2:
return True
e = int(n ** .5) + 1
for i in range(2, e + 1):
if n % i == 0:
return False
else:
return True

def power_up(n):
# helper function return the next 10 power
i = 1
while 1:
if n < i:
return i
i*=10

def conc(x,y):
# helper function check if xy and yz is prime
if not is_prime((x*power_up(y))+y):
return False
else:
return is_prime(y*power_up(x)+x)

def conc3(x,y,z): # not use, it did not improve the performance
a = conc(x,y)
if not a:
return False
b = conc(x,z)
if not b:
return False
c = conc(y,z)
if not c:
return False
return True

one = []
two = []
three = []
four = []
found = 0

for i in prime():
if found:
break
try:
if i > sum_:
break
except:
pass
one += [i]
for j in one[:-1]:  # on the fly list
if conc(i,j):
two += [[i, j]]
for _, k in two: # check against k only if it is in a two pair
if _ == j:
for x in [i, j]:
if not conc(x,k):
break
else:
three += [[i, j, k]]
for _, __, l in three:
if _ == j and __ == k:

for x in [i, j, k]:
if not conc(x,l):
break
else:
four += [[i, j, k, l]]
# print(i, j, k, l)
for _, __, ___, m in four:
if _ == j and __ == k and ___ == l:
for x in [i, j, k, l]:
if not conc(x,m):
break
else:
a = [i, j, k, l, m]
t2 = time.time()
try:
if (
sum(a) < sum_
):  # assign sum_ with the first value found
sum_ = sum(a)
except:
sum_ = sum(a)
print(
f"the sum now is {sum(a)}, the sum of [{i}, {j}, {k}, {l}, {m}], found in {t2-t1:.2f}sec"
)
if i > sum_:
# if the first element checked is greater than the found sum, then we are sure we found it,
# this is the only way we can be sure we found it.
# it took 1 and a half min to find the first one, and confirm that after 42min.
# my way is not fast, but what I practised here is to find the number without a guessed boundary

found = 1
print(
f"the final result is {sum_}"
)


I found the first candidate in 75 sec which I think is to long. I want to see if anyone can give me some suggestion on how to improve the performance.