题解 | #素数伴侣#
素数伴侣
https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e
import math def check_prime(num): for i in range(2, int(math.sqrt(num)+1)): if num%i == 0: return False return True def find_even(odd, evens, choose, visited): for j, even in enumerate(evens): if check_prime(odd + even) and not visited[j]: visited[j] = True # 假设第j个 位置的evens还没有被choose; # 或者被choose了,但是之前choose它的odd可以选择一个新的even。 # 那么当前odd可以选择第j个even。 if choose[j]==0 or find_even(choose[j], evens, choose, visited): choose[j] = odd return True return False N = int(input().strip()) all_nums = list(map(int, input().strip().split())) odds = [] # 奇数集合 evens = [] # 偶数集合 for num in all_nums: if num%2 == 0: evens.append(num) else: odds.append(num) count = 0 choose = [0]*len(evens) for odd in odds: visited = [False]*len(evens) if find_even(odd, evens, choose, visited): count += 1 print(count)