题解 | #素数伴侣#

import math def is_prime(x): for i in range(2,int(math.sqrt(x)+2)):##如果只+1那么当x=2时，就会出现range(2,2) if x%i==0: return False return True

def prime_dic(odds,evens):##建立一个伴侣字典，通过查字典就可以知道是否可以称为伴侣，这样就不必重复计算 dic ={} for odd in odds: for even in evens: if is_prime(odd+even): dic['%d,%d'%(odd,even)]=1 else: dic['%d,%d'%(odd,even)]=0 return dic

def find(odd,evens,choose,visited):##最难以理解的一步，只能通过带入简单例子去理解，每个参数都至关重要 for j,even in enumerate(evens): if dic['%d,%d'%(odd,even)]==1 and not visited[j]: visited[j]=True if choose[j]==0 or find(choose[j],evens,choose,visited): choose[j]=odd return True

while True: try: n = int(input()) num = list(map(int,input().split())) odds=[] evens=[] count=0 for i in num: if i%2==0: evens.append(i) else: odds.append(i) dic = prime_dic(odds,evens) choose=[0]*len(evens) for i in odds: visited=[False]*len(evens) if find(i,evens,choose,visited): count+=1 print(count) except: break