题目

描述

题目描述 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

输入:

有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。

输出:

输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。

数据范围： $$ 1≤n≤100 $$

输入的数据大小满足 $$ 2≤val≤30000 $$

输入描述：

输入说明 1 输入一个正偶数 n 2 输入 n 个整数

输出描述：

求得的“最佳方案”组成“素数伴侣”的对数。

示例

示例1

输入：

4
2 5 6 13

输出：

2

示例2

输入：

2
3 6

输出：

0

算法

思路

如果是素数，一定是奇数加偶数才有可能是素数，所以将要配对的数分为两组，一组是奇数，一组是偶数，通过匈牙利算法求得最大的配对数。

配对的思路是，可以把偶数和奇数当做两组数据来互相配对，首先一个奇数和一个偶数已经配对成功，后边另一个奇数发现它和这个偶数也可以配对，那么它就尝试拆散原有的奇数和偶数，前提是前面已经配对的奇数可以再找到一个配对的偶数，否则不能拆散。

这样递归，直到能够在奇数偶数中找出最多对的配对数。

还有一个很直观的解释：

数在循环过程中，不管谁和谁配对，如果后来的数也能和同一个数配对，且先配对的数能与其他数配对，则先配对的数和别的数配对，后来的数也能配对，循环的顺序仅仅可能会影响配对关系，不影响最后配对成功的最大值。更改配对关系的前提是能增加配对的数量，否则配对关系是否改变不影响最后的结果，因为如果你能和多个数配对，则你总能和某个数配对，如果你只能和某个数配对，那么需要看对方是否已经配对，对方配对的数是否能和其他数配对，如果不能，则不会增加最后配对成功的数量，则配对关系不会改变。即是你和他和某一个数配对，对配对总数来说都是一样的，先来后到。

代码

import math

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 2):
        if n % i == 0:
            return False
    return True


def find(even, visited, choose, odds):
    for i,odd in enumerate(odds):
        if is_prime(even+odd) and not visited[i]:
            visited[i] = True
            if choose[i] == 0 or find(choose[i],visited,choose,odds):
                choose[i] = even
                return True
    
    return False


while True:
    try:
        num = int(input())
        a = [int(x) for x in input().split()]
        count = 0
        odds = [x for x in a if x % 2 != 0]
        evens = [x for x in a if x % 2 == 0]
        choose = [0] * len(odds)
        for even in evens:
            visited = [False] * len(odds)
            if find(even, visited, choose, odds):
                count += 1
        print(count)
    except:
        break

知识点

• 匈牙利算法