一、题目

🔸题目描述

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

🔸输入输出

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

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

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

🔸样例1

🔸样例2

输入
2
3 6


输出
0

二、思路解析

首先定义两个list容器，分别存储输入整数中的奇数和偶数。
然后利用匈牙利算法找到“素数伴侣”对数最多时的配对数。匈牙利算法的核心思想是先到先得，能让就让。
最后输出“素数伴侣”最多时的对数。

举例说明：如图所示，首先A1和B2配对（先到先得），然后轮到A2，A2也可以和B2配对，这时候B2发现A1还可以和B4配对，所以放弃了A1，选择和A2组成伴侣（能让就让）。接着A3直接和B1配对（先到先得）。最后A4尝试与B4配对，但是这样A1就只能与B2配对，而A2就找不到伴侣了，一层层递归下来，发现不可行，所以A4不能与B4配对。

三、代码参考

import java.util.Scanner;
import java.util.ArrayList;

public class Main{
    
    static int max=0;
    public static void main(String[] args){
        //标准输入
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //输入正偶数
            int n=sc.nextInt();
            //用于记录输入的n个整数
            int[] arr=new int[n];
            //用于存储所有的奇数
            ArrayList<Integer> odds=new ArrayList<>();
            //用于存储所有的偶数
            ArrayList<Integer> evens=new ArrayList<>();
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
                //将奇数添加到odds
                if(arr[i]%2==1){
                    odds.add(arr[i]);
                }
                //将偶数添加到evens
                if(arr[i]%2==0){
                    evens.add(arr[i]);
                }
            }
            //下标对应已经匹配的偶数的下标，值对应这个偶数的伴侣
            int[] matcheven=new int[evens.size()];
            //记录伴侣的对数
            int count=0;
            for(int j=0;j<odds.size();j++){
                //用于标记对应的偶数是否查找过
                boolean[] v=new boolean[evens.size()];
                //如果匹配上，则计数加1
                if(find(odds.get(j),matcheven,evens,v)){
                    count++;
                }
            }
            System.out.println(count);
        }   
    }
    
    //判断奇数x能否找到伴侣
    private static boolean find(int x,int[] matcheven,ArrayList<Integer> evens,boolean[] v){
        for(int i=0;i<evens.size();i++){
            //该位置偶数没被访问过，并且能与x组成素数伴侣
            if(isPrime(x+evens.get(i))&&v[i]==false){
                v[i]=true;
                /*如果i位置偶数还没有伴侣，则与x组成伴侣，如果已经有伴侣，并且这个伴侣能重新找到新伴侣，
                则把原来伴侣让给别人，自己与x组成伴侣*/
                if(matcheven[i]==0||find(matcheven[i],matcheven,evens,v)){
                    matcheven[i]=x;
                    return true;
                }
            }
        }
        return false;
    }
    //判断x是否是素数
    private static boolean isPrime(int x){
        if(x==1) return false;
        //如果能被2到根号x整除，则一定不是素数
        for(int i=2;i<=(int)Math.sqrt(x);i++){
            if(x%i==0){
                return false;
            }
        }
        return true;
    }
}


--------------------------------------------------------



/*
如果是素数，一定是奇数和偶数结合（奇数）才有可能是素数，所以将需要配对的数分为两组，一组是奇数，一组是偶数，通过匈牙利算法求得最大的配对数配对的思路是：
可以把偶数和奇数当初来相亲的一些男女，首先一对男女相亲成功结婚了，然后另一个男生发现他和这个女生也合适，他就拆散这两个人，自己和这个女生结婚，让这个前夫哥再寻找自己的结婚对象，这样递归，直到能够再这些相亲的男女中找出最多对的夫妻

*/
import math
def check(num): #判断是否是素数
    for i in range(2,int(math.sqrt(num)) + 2): #除去1和本身的数没有其他的因子称为素数，但其实检验到int(math.sqrt(num)) + 1即可（数学证明略），不然会超时
        if(num % i == 0):
            return False
    return True

def find(odd, visited, choose, evens): #配对的过程
    for j,even in enumerate(evens):  
        if check(odd+even) and not visited[j]: #如果即能配对，这两个数之前没有配过对（即使两个不能配对visit值为0，但是也不能过是否是素数这一关，所以visit就可以
        看为两个能配对的素数是否能配对）
            visited[j] = True #代表这两个数能配对
            if choose[j]==0 or find(choose[j],visited,choose,evens): #如果当前奇数没有和任何一个偶数现在已经配对，那么认为找到一组可以连接的，如果当前的奇数已经配对，那么就让那个与之配对的偶数断开连接，让他再次寻找能够配对的奇数
                choose[j] = odd #当前奇数已经和当前的偶数配对
                return True 
    return False 如果当前不能配对则返回False

while True:
    try:
        num = int(input())
        a = input()
        a = a.split()
        b = []
        count = 0
        for i in range(len(a)):
            a[i] = int(a[i])
        evens = []
        odds = []
        for i in a: #将输入的数分为奇数和偶数
            if(i % 2 == 0):
                odds.append(i)
            else:
                evens.append(i)
        choose = [0]*len(evens) #choose用来存放当前和这个奇数配对的那个偶数
        for odd in odds:
            visited = [False]*len(evens) #visit用来存放当前奇数和偶数是否已经配过对
            if find(odd,visited,choose,evens):
                count += 1
        print(count)
    except:
        break

    

--------------------------------------------------------------


//两数相加要为素数，则这两个数必然一个奇数一个为偶数
//将输入的数据分为奇数和偶数两部分
#include <math.h>
#define MAX_COUNT 100
int even[MAX_COUNT];   			 //存储偶数
int odd[MAX_COUNT];      		 //存储奇数
int line[MAX_COUNT][MAX_COUNT];  //标记以此下标(x,y)的两个数之和是素数
int used[MAX_COUNT];			 //标记此下标对应的奇数值是否被使用
int evenCount = 0;      		 //偶数计数
int oddCount = 0;				 //奇数计数
/* 判断是不是素数 */
int IsPrime(int num)
{
    for (int i = 2;i <= sqrt(num);i++) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}

/* 遍历标记出符合两数之和为素数的组合 */
void Line()
{
    for (int i = 0;i < evenCount;i++) {
        for (int j = 0;j < oddCount;j++) {
            if (IsPrime(even[i] + odd[j]) == 1) {
                line[i][j] = 1;
            }
        }
    }
}

/* 将数组的元素分为偶数和奇数两部分，并做出标记 */
void IsEvenOrOdd(int num[], int n)
{
    for (int i = 0;i < n;i++) {
        if (num[i] % 2 == 0) {
            even[evenCount++] = num[i];
        } else {
            odd[oddCount++] = num[i];
        }
    }
    Line();
}
int oddEven[MAX_COUNT]; //存储第j个奇数匹配的偶数下标
/* 匈牙利算法，直到匹配的数，返回1，否则返回0 */
int FindPrimeMate(int n)
{
    for (int j = 0;j < oddCount;j++) {
        if ((line[n][j] == 1) && (used[j] == 0)) {
            used[j] = 1;
            if ((oddEven[j] == -1) || FindPrimeMate(oddEven[j])) {
                oddEven[j] = n;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int n = 0;
    int sum = 0;
    int num[MAX_COUNT] = {0};
    scanf("%d", &n);
    memset(oddEven, -1, MAX_COUNT*sizeof(int));
    for (int i = 0;i < n;i++) {
        scanf("%d", &num[i]);
    }
    IsEvenOrOdd(num, n);
    /* 遍历所有偶数，查找出与之匹配的奇数 */
    for (int i = 0;i < evenCount ;i++) {
    	/* 每一轮清除used标记 */
        memset(used, 0, MAX_COUNT);
        sum += FindPrimeMate(i);
    }
    printf("%d", sum);
    return 0;
}