Печать первой комбинации среди различных комбинаций

Question

Итак, у меня есть вопрос:

Если задано четное число (больше 2), вернуть два простых числа, сумма которых будет равна данному числу. Возможны несколько комбинаций. Выведите только первую такую ​​пару

Это для дополнительной справки:

* Ввод: Первая строка содержит T, количество тестовых случаев. Следующие строки T состоят из числа, для которого мы найдем два простых числа.

Примечание: число всегда будет четным числом.

Вывод: для каждого теста выведите два простых числа разделены пробелом, так что меньшее число появляется первым. Ответ для каждого теста должен быть в новой строке.

Ограничения: 1 ≤ T ≤ 70

2

Пример:

Вход:

5, 74, 1024, 66, 8, 9990

Выход: 3 71, 3 1021, 5 61, 3 5, 17 9973

Вот что Я попытался:

import math
def prime(n):

    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True       

T = int(input("No of inputs: ")) #T is the no of test cases

input_num = []
for i in range(0,T):
    input_num.append(input())

lst2= []
if T in range(1,71):
    for i in input_num:
        if (i in range(3,1000)) and (i % 2 == 0):
            for j in range(0,i):
                if prime(j) == True:
                    lst2.append(j)
                for x in lst2:
                    for y in lst2:
                        if x + y == j:
                            print(x,end = ' ')
                            print(y)

Это только принимает входные данные, но не возвращает выходные данные.

Также мой код в настоящее время предназначен для всех комбинаций, но я хочу только первую пару, и я не в состоянии сделать это

Answer 1

Я нашел более элегантное решение этой проблемы здесь . Java, C, C ++ et c версии решения также присутствуют там. Я собираюсь дать решение python3.

# Python 3 program to find a prime number 
# pair whose sum is equal to given number 
# Python 3 program to print super primes 
# less than or equal to n. 

# Generate all prime numbers less than n. 
def SieveOfEratosthenes(n, isPrime): 

    # Initialize all entries of boolean 
    # array as True. A value in isPrime[i] 
    # will finally be False if i is Not a 
    # prime, else True bool isPrime[n+1] 
    isPrime[0] = isPrime[1] = False
    for i in range(2, n+1): 
        isPrime[i] = True

    p = 2
    while(p*p <= n): 
        # If isPrime[p] is not changed, 
        # then it is a prime 
        if (isPrime[p] == True): 
            # Update all multiples of p 
            i = p*p 
            while(i <= n): 
                isPrime[i] = False
                i += p 
        p += 1

# Prints a prime pair with given sum 
def findPrimePair(n):
    # Generating primes using Sieve 
    isPrime = [0] * (n+1) 
    SieveOfEratosthenes(n, isPrime) 

    # Traversing all numbers to find  
    # first pair 
    for i in range(0, n): 
        if (isPrime[i] and isPrime[n - i]): 
            print(i,(n - i)) 
            return

# Driven program 
n = 74
findPrimePair(n)