3
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ Hey, why do you keep editing my post without any useful comments? \$\endgroup\$
    – peternish
    Nov 10, 2023 at 23:39
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – greybeard
    Nov 11, 2023 at 10:29

1 Answer 1

2
\$\begingroup\$

Eliminate 2 and 5 from your sieve!

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.