Cfrtjryk

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.