HJ28 素数伴侣

 1 '''
 2 #思路
 3 #递归方法：
 4 举例，从头考试两两成对，如2，5，6，13，12，11，10
 5 1、第一次探索 2，5|6，13|12，11|10，记录素数伴侣的对数
 6 2、后释放一对12，11，重新配对2，5|6，13|12|11，10；2，5|6，13|11|12，10；
 7 共2组，记录素数伴侣的对数
 8 （3、若数列刚好成对，需要释放两队后重新配对，如数列少一个元素10。
 9 重新配对2，5|6，12|13，11；2，5|13，12|6，11，共2组，分别记录素数对数
10 4、再释放一队。
11 重新配对2，12|6，13|5，11；12，5|6，13|2，11；2，6|5，13|12，11；
12        6，5|2，13|12，11；共4组，分别记录素数对数）
13 5、再释放一队6，13，重新配对
14      2，5|6，12|13，11|10；2，5|12，13|6，11|10；
15      2，5|6，11|12|13，10；2，5|13，11|12|6，10
16      2，5|6，12|11|13，10；2，5|13，12|11|6，10；共6组，分别记录素数伴侣的对数
17 依次递推
18 最重要的是recouple的方法:
19 '''
20 def check(n):
21     for i in range(2,n):
22         if n%i==0:
23             return False  
24     return True
25 def recouple(couple,c,i):
26     coup=couple.copy()
27     t=c.copy()
28     #print(c,i)
29     if i%2==0:
30         couple.append([c[0],c[i]])
31         couple.append([c[1],c[i+1]])
32         t[0],t[1],t[i],t[i+1]=0,0,0,0        
33     if i%2!=0:
34         couple.append([c[0],c[i]])
35         couple.append([c[1],c[i-1]])
36         t[0],t[1],t[i],t[i-1]=0,0,0,0
37     for i in range(4):
38         t.remove(0)
39     for i in range(0,len(t),2):        
40         couple.append(t[i:i+2])
41     #print(couple)
42     return coup
43 def reduce(temp):
44     tem=[]
45     for i in temp:
46         for j in i:
47             tem.append(j)
48     return tem
49 def recursion(a,couple,perc,flag=1,release=0):
50     if release>=len(couple)+1 and len(couple)!=1:
51         #print("done",release,couple)
52         return
53     if len(couple)>=len(a)//2:
54         c=0
55         for i in couple:
56             if check(sum(i)):
57                 c+=1            
58         res.append(c)
59     if len(couple)==1:
60         #print("done1")
61         return
62     
63     if flag==1:
64         for temp in range(0,len(a),2):
65             couple.append(a[temp:temp+2])
66         perc=couple.copy()
67         recursion(a,couple,perc,flag=0,release=2)      
68     if flag==0:
69         #print(release)
70         temp=perc[-release:]
71         tem=reduce(temp)
72         couple=perc[:-release]
73         for i in range(2,len(tem)): # 对释放出来的couple数一一互换               
74             coup=recouple(couple,tem,i)
75             c=0
76             for i in couple:
77                 if check(sum(i)):
78                     c+=1            
79             res.append(c)
80             couple=coup.copy()
81         couple=perc
82         recursion(a,couple,perc,flag=0,release=release+1) #逐渐增加释放couple数。
83 no=int(input())
84 a=list(map(int,input().split()))      
85 res=[]
86 perc=[]
87 couple=[]
88 recursion(a,couple,perc)
89 print(max(res))