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)
