题解 | #素数伴侣#

解题思路： 1.判断一个数是否为素数：在这里需要注意的是全部数判断会超时，所以选择半位数来判断可以节省时间。选用原理：一个数能被另一个数除尽，则这个数也能被它的2倍数除尽，一个数不能被另一个数除尽则也不能被它的2倍数除尽。 2.判断最大匹配数： 这个是参考已有的答案来的，一个列表里的数与另一个列表里的每一个数判断，如果他们的和是素数就标记，若这个数还有另一个匹配的数，则看看之前匹配的数是否还有其他匹配的数，有则这个数就被当前数替代，没有则跳过。如此一来得到的数即为最大匹配数 3.数的分配与具体判断实现： 奇数和奇数相加与偶数和偶数相加得到的是偶数不可能是素数，只能是奇数和偶数相加才可能存在素数。因此将所有可匹配的数按奇数和偶数分为两个列表。然后让每一个奇数与所有偶数列表的数去匹配看相加的和是否为素数，如果是则加1。最终将计算的数打印出来

def get_primenum(s):
    if s<4:
        return True
    #通过从2到它的平方根之间没有可除尽的数来判断这个数是否为素数。原理：一个数与另一个数能除尽则也能除尽这个数的2倍数。若直接判断从2到这个数之间的数则会耗费大量的时间来计算导致超时。
    for i in range(2,int(s**0.5)+1):
        if s%i==0:
            return False
    return True
    
def find_even(evens,previous_select,final_select,odd):
    for i, even in enumerate(evens):
        if get_primenum(even+odd) and previous_select[i]==0:
            previous_select[i]=1
            #判断第i位偶数是否被匹配或者它的匹配奇数是否有其他选择，如果有其他选择，则当前的奇数匹配第i位偶数
            if final_select[i]==0 or find_even(evens, previous_select, final_select, final_select[i]):
                final_select[i]=odd
                return True
    return False

while True:
    try:
        N=int(input())
        list0=list(map(int,input().split(' ')))
        count0=0
        evens,odds=[],[]
        for list1 in list0:
            if list1%2==0:
                evens.append(list1)
            else:
                odds.append(list1)
        final_select=[0]*len(evens)
        for odd in odds:
            previous_select=[0]*len(evens)
            if find_even(evens, previous_select, final_select, odd):
                count0 +=1
        print(count0)
    except:
        break