Project Euler Problem 060

Statement

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.

Solution

Brute-force approach solution using sets in Python.

At first I calculate the primes lower than 10000, then for each of them I test them against each of the current sets, in case it can be inserted, a new set is created with all the numbers of the set plus the new value.

This process continues until a set of size 5 is found.

from CommonFunctions import find_primes_less_than, is_prime
 
primes = set()
non_primes = set()
 
def determine_prime(n):
    if n in primes:
        return True
    if n in non_primes:
        return False
    if is_prime(n):
        primes.add(n)
        return True
    else:
        non_primes.add(n)
        return False
 
if __name__ == '__main__':
    list_of_sets = []
    maxim = 0
    for prime in find_primes_less_than(10000)[1:]:
        for i in range(len(list_of_sets)):
            s = list_of_sets[i]
            enter = True
            str_prime = str(prime)
            for n in s:
                str_n = str(n)
                if not determine_prime(int(str_n + str_prime)) or not determine_prime(int(str_prime + str_n)):
                    enter = False
                    break
            if enter:
                newset = s.copy()
                newset.add(prime)
                if len(newset) == 5:
                    print("The result is:", sum(newset))
                    exit(0)
                list_of_sets.append(newset)
        list_of_sets.append(set([prime]))

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License