python-3.x - 打印各种组合中的第一个组合

Question

所以我有一个问题:

给定一个偶数(大于 2)，返回两个总和等于给定数的素数。有几种可能的组合。只打印第一个这样的对

这是供额外引用:

*输入:第一行包含T，测试用例的数量。接下来的 T 行每行包含一个数字，我们将找到两个素数。

注意:该数字始终为偶数。

输出:对于每个测试用例，打印两个以空格分隔的素数，这样较小的数字首先出现。每个测试用例的答案必须换行。

约束条件:1≤T≤70

2 < N ≤ 10000

例子:

输入:

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

我找到了解决这个问题的更优雅的方法here .那里也有 Java、C、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)