# Project Euler 60: Prime Pair Sets

Project Euler Prime Pair Sets:

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.

Extension:
Find the sum of all sets of K primes for which any two primes (smaller than N) concatenate to produce another prime.
Print the sums in sorted order.

How can I optimize the code below?

from itertools import combinations, permutations

input_value = input().split()
N = int(input_value[0])
k = int(input_value[1])

# Find all primes which is smaller than N
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
return [i for i, is_prime in enumerate(primes) if is_prime]

# Find the criteria I have to run iteration
def find_criteria(prime_list, k):
max_num_list = prime_list[-k:]
max_num_list_sorted = sorted(max_num_list, key=lambda x: [int(d) for d in str(x)], reverse=True)
max_criteria = ''
for i in max_num_list_sorted:
max_criteria += str(i)
return int(max_criteria)

# Check if a list of k prime numbers can be the solution to the problem
def check_solution(prime_list_combination, prime_list_max, k):
prime_list_permutation = list(permutations(prime_list_combination, k))
for i in prime_list_permutation:
k_str = ''
for j in i:
k_str += str(j)
if int(k_str) not in prime_list_max:
return False
return True

prime_list = sieve_of_eratosthenes(N)
max_criteria = find_criteria(prime_list, 2)
prime_list_max = sieve_of_eratosthenes(max_criteria)
prime_list_combination = list(combinations(prime_list, k))
solution_list = []

print(len(prime_list_combination))

for i in prime_list_combination:
if check_solution(i, prime_list_max, 2) == True:
solution_list += [sum(i)]

solution_list = sorted(solution_list)
for i in solution_list:
print(i)

• Hey, why do you keep editing my post without any useful comments? Nov 10 at 23:39
• SE comments are for improving the post they comment. Specificially, they are not for answering, and any insightful observation about the code would constitute a valid CR answer. Sometimes it seems easier to just go ahead with an improvement than to suggest and motivate it - you can do side-by-side comparisons following the edited … hyperlink below the post. Nov 11 at 10:29

Any 2+ digit prime cannot end in a 2 or a 5, as these will be multiples of 2 and 5 respectively. Thus neither 2 nor 5 cannot be part of any prime pair set.
As N increases, the gain of eliminating two candidates may become negligible, but it will always be non-zero, and it is trivial to implement.