题解 | 素数伴侣

# 贪心算法求解
N = int(input())
num = list(map(int, input().split()))
M = max(num)
# 素数判定
def is_prime(x):
    if x in (2, 3, 5):
        return True
    if x < 7:
        return False
    for i in range(2, int(x/2)):
        if x % i == 0:
            return False
    return True
# 素数由基数和偶数相加得到（除2以外），故先分奇数偶数
jishu = []
oushu = []
for k in num:
    if k % 2 == 0:
        oushu.append(k)
    else:
        jishu.append(k)
jishu.sort(reverse = True)
if len(jishu) == 0:
    print(0)
elif len(oushu) == 0:
    print(int(jishu.count(1)/2))
else:
    # 奇数配偶数，以奇数为基准，优先配能够配对数量少的奇数
    # 先求奇数配对数量，再配对最少项，依次迭代至结束。
    count = 0 # 记配对数
    count1 = 0 # 记1
    # 配对数列表
    peiduishu = []
    for i in range(len(jishu)):
        peiduishu.append([0])
        for j in range(len(oushu)):
            if j > 0:
                peiduishu[i].append(0)
            if is_prime(jishu[i] + oushu[j]):
                peiduishu[i][j] = 1
    def delete_ji(peiduishu,i):
        peiduishu = peiduishu[:i]+ peiduishu[i+1:]
        return peiduishu
    def delete_ou(peiduishu,j):
        for i in range(len(peiduishu)):
            peiduishu[i] = peiduishu[i][:j]+ peiduishu[i][j+1:]
        return peiduishu
    def peiduishu2jiou(peiduishu):
        if len(peiduishu) == 0:
            return [],[]
        # 奇数配对数量列表
        peiduishu_ji = []
        for i in range(len(peiduishu)):
            peiduishu_ji.append(sum(peiduishu[i]))
        # 偶数配对数量列表
        peiduishu_ou = []
        for j in range(len(peiduishu[0])):
            peiduishu_ou.append(0)
            for i in range(len(peiduishu)):
                peiduishu_ou[j] += peiduishu[i][j]
        return peiduishu_ji, peiduishu_ou 
    while(len(jishu)):
        # 优先移除非配对数
        peiduishu_ji, peiduishu_ou = peiduishu2jiou(peiduishu)
        while 1:
            try:
                n = peiduishu_ji.index(0)
                if jishu[n] == 1:
                    count1 += 1
                jishu = jishu[:n] + jishu[n+1:]
                peiduishu = delete_ji(peiduishu,n)
            except:
                try:
                    n = peiduishu_ou.index(0)
                    oushu = oushu[:n] + oushu[n+1:]
                    peiduishu = delete_ou(peiduishu,n)
                except:
                    break
            peiduishu_ji, peiduishu_ou = peiduishu2jiou(peiduishu)
        # 再删配对数，奇数配对数量最少的，同时配对偶数配对数数量少的
        if len(jishu) * len(oushu) == 0:
            break
        nrm_ji = peiduishu_ji.index(min(peiduishu_ji))
        nrm_ou_list = []
        for j in range(len(oushu)):
            if peiduishu[nrm_ji][j] == 1:
                nrm_ou_list.append(j)
        nrm_ou = nrm_ou_list[0]
        for i in nrm_ou_list:
            if peiduishu_ou[nrm_ou] > peiduishu_ou[i]:
                nrm_ou = i
        # 移除
        oushu.remove(oushu[nrm_ou])
        jishu.remove(jishu[nrm_ji])
        peiduishu = delete_ji(peiduishu,nrm_ji)
        peiduishu = delete_ou(peiduishu,nrm_ou)
        count += 1
    print(count + int(count1/2))