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)

这只是接受输入而不是返回输出。

此外，我的代码目前适用于所有组合，但我想要的只是第一对，我无法做到这一点

标签： python-3.xloops

Answer 1

我在这里找到了解决这个问题的更优雅的方法。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)