题意整理。

• 输入N（N为偶数）个正整数，从其中挑选出若干对组成“素数伴侣”。
• 问怎么挑选，可以使得“素数伴侣”的对数最多。
• 如果两个正整数的和为素数，则这两个正整数称之为“素数伴侣”。

方法一（匈牙利算法）

1.解题思路

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

图解展示（匈牙利算法）：

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

2.代码实现

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;
    }
}

3.复杂度分析

• 时间复杂度：假设输入的奇数的数目为p，输入的偶数的数目为q，则find函数的时间复杂度为$O(q^2)O(q^2)$，因为循环内还嵌套了一个递归，虽然还有一个判断是否是素数的函数，但是题目中输入的数据范围在1-100之间，所以这个判断素数的函数的时间复杂度为$O(1)O(1)$。最坏情况下，奇数和偶数的数目相等，均为$n\mathrm{/}2n/2$，此时find函数的复杂度为$O(n^2)O(n^2)$，需要对所有的奇数执行find，所以时间复杂度为$O(n^3)O(n^3)$。
• 空间复杂度：需要额外大小为p和q的list容器分别存储对应的奇数和偶数，p、q均不大于n，所以空间复杂度为$O(n)O(n)$。

方法二（利用io流）

1.解题思路

思路和方法一基本一致，不同的是通过io流操作来处理输入的数据。

2.代码实现

import java.io.*;
import java.util.ArrayList;

public class Main{
    
    static int max=0;
    public static void main(String[] args) throws Exception{
        //io输入
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s;
        while((s=br.readLine())!=null){
            //输入正偶数n
            int n=Integer.parseInt(s);
            //输入n个整数
            String[] arr=br.readLine().split(" "); 
            //用于存储所有的奇数
            ArrayList<Integer> odds=new ArrayList<>();
            //用于存储所有的偶数
            ArrayList<Integer> evens=new ArrayList<>();
            for(int i=0;i<n;i++){
                int num=Integer.parseInt(arr[i]);
                //将奇数添加到odds
                if(num%2==1){
                    odds.add(num);
                }
                //将偶数添加到evens
                if(num%2==0){
                    evens.add(num);
                }
            }
            //下标对应已经匹配的偶数的下标，值对应这个偶数的伴侣
            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;
    }
}

3.复杂度分析

• 时间复杂度：假设输入的奇数的数目为p，输入的偶数的数目为q，则find函数的时间复杂度为$O(q^2)O(q^2)$，因为循环内还嵌套了一个递归，虽然还有一个判断是否是素数的函数，但是题目中输入的数据范围在1-100之间，所以这个判断素数的函数的时间复杂度为$O(1)O(1)$。最坏情况下，奇数和偶数的数目相等，均为$n\mathrm{/}2n/2$，此时find函数的复杂度为$O(n^2)O(n^2)$，需要对所有的奇数执行find，所以时间复杂度为$O(n^3)O(n^3)$。
• 空间复杂度：需要额外大小为p和q的list容器分别存储对应的奇数和偶数，p、q均不大于n，所以空间复杂度为$O(n)O(n)$。