题解 | #素数伴侣#

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


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        //输入:有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //输入的数字先分好奇数、偶数两组
        List<Integer> evenNumberList = new ArrayList<>();//偶数
        List<Integer> oddNumberList = new ArrayList<>();//奇数
        if(n<=1){//数据范围：1≤n≤100 （从已有的 N （ N 为偶数）个正整数中挑选），所以N>=2 ，
            //输入的数据j大小满足 2≤val≤30000
        }else {
            for (int i = 0; i < n; i++) {
                int j = sc.nextInt();
                if(j%2==0){// 偶数：可以被2整除的整数
                    evenNumberList.add(j);
                }else {
                    oddNumberList.add(j);
                }
            }
        }
        int evenSize = evenNumberList.size();//记录偶数个数
        int count = 0;//记录素数伴侣的对数
        int[] evensPartner = new int[evenSize];//记录偶数匹配的 奇数伴侣
        for (Integer odd : oddNumberList ) {//奇数列表 去寻找唯一偶数
            int[] used = new int[evenSize]; //用于标记这个偶数 是否 匹配伴侣   每次更换奇数伴侣都会重新更新列表。
            //唯一奇数odd 在偶数列表中 寻找 未匹配的 素数伴侣。
            if(find(odd,evenNumberList,used,evensPartner)){
                count++; //匹配成功，总对数加一
            }
        }
        //输出:输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
        System.out.println(count);
        sc.close();
    }
    private static boolean find(Integer odd, List<Integer> evenNumberList, int[] used, int[] evensPartner) {
        for (int i = 0; i < evenNumberList.size(); i++) {
            if(isPrime(odd + evenNumberList.get(i)) && used[i] == 0){
                //是素数并且偶数没有被使用过
                used[i] = 1;//偶数被使用，标记1。
                /*   如果第i个偶数没有伴侣，或者第i个偶数原来有奇数伴侣（evensPartner[i]!=0），
                  并且原来的奇数伴侣能够重新找到伴侣的话(会返回true)(这里有递归调用)，则奇数odd可以设置为第i个偶数的伴侣。
                这里采用了匈牙利算法：核心思想是先到先得，能让就让。
                  如果原来的奇数伴侣不能找到其他伴侣，则不让，每一次find都返回false。*/
                if(evensPartner[i] == 0 || find(evensPartner[i], evenNumberList,used,evensPartner )){
                    evensPartner[i] = odd;
                    return true;
                }
            }
        }
        return false; // 遍历完偶数都没有可以与传入奇数做伴侣的，该奇数值没有配对的偶数
    }
    /*质数(prime number)又称素数，有无限个。素数是一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。
    换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。
    0和1既不是质数也不是合数，最小的质数是2
    * */
    private static boolean isPrime(int TheSumOfOddAndEvenNumbers) {//判断这个奇数和这个偶数相加是否是素数
        if(TheSumOfOddAndEvenNumbers<=1){
            return false;
        }else {
            for (int j = 2; j < TheSumOfOddAndEvenNumbers; j++) {
                if( TheSumOfOddAndEvenNumbers % j == 0){
                    return false;
                }
            }
        }
        return true;
    }
}
/*参考引用
        本系列归档至******************************************
        《Java 数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action
        《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html
*/

参考引用

本系列归档至******************************************

《Java 数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action

《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html

方法一（匈牙利算法）

1.解题思路

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

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

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

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


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        //输入:有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //输入的数字先分好奇数、偶数两组
        List<Integer> evenNumberList = new ArrayList<>();//偶数
        List<Integer> oddNumberList = new ArrayList<>();//奇数
        if(n<=1){//数据范围：1≤n≤100 （从已有的 N （ N 为偶数）个正整数中挑选），所以N>=2 ，
            //输入的数据j大小满足 2≤val≤30000
        }else {
            for (int i = 0; i < n; i++) {
                int j = sc.nextInt();
                if(j%2==0){// 偶数：可以被2整除的整数
                    evenNumberList.add(j);
                }else {
                    oddNumberList.add(j);
                }
            }
        }
        int evenSize = evenNumberList.size();//记录偶数个数
        int count = 0;//记录素数伴侣的对数
        int[] evensPartner = new int[evenSize];//记录偶数匹配的 奇数伴侣
        for (Integer odd : oddNumberList ) {//奇数列表 去寻找唯一偶数
            int[] used = new int[evenSize]; //用于标记这个偶数 是否 匹配伴侣   每次更换奇数伴侣都会重新更新列表。
            //唯一奇数odd 在偶数列表中 寻找 未匹配的 素数伴侣。
            if(find(odd,evenNumberList,used,evensPartner)){
                count++; //匹配成功，总对数加一
            }
        }
        //输出:输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
        System.out.println(count);
        sc.close();
    }
    private static boolean find(Integer odd, List<Integer> evenNumberList, int[] used, int[] evensPartner) {
        for (int i = 0; i < evenNumberList.size(); i++) {
            if(isPrime(odd + evenNumberList.get(i)) && used[i] == 0){
                //是素数并且偶数没有被使用过
                used[i] = 1;//偶数被使用，标记1。
                /*   如果第i个偶数没有伴侣，或者第i个偶数原来有奇数伴侣（evensPartner[i]!=0），
                  并且原来的奇数伴侣能够重新找到伴侣的话(会返回true)(这里有递归调用)，则奇数odd可以设置为第i个偶数的伴侣。
                这里采用了匈牙利算法：核心思想是先到先得，能让就让。
                  如果原来的奇数伴侣不能找到其他伴侣，则不让，每一次find都返回false。*/
                if(evensPartner[i] == 0 || find(evensPartner[i], evenNumberList,used,evensPartner )){
                    evensPartner[i] = odd;
                    return true;
                }
            }
        }
        return false; // 遍历完偶数都没有可以与传入奇数做伴侣的，该奇数值没有配对的偶数
    }
    /*质数(prime number)又称素数，有无限个。素数是一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。
    换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。
    0和1既不是质数也不是合数，最小的质数是2
    * */
    private static boolean isPrime(int TheSumOfOddAndEvenNumbers) {//判断这个奇数和这个偶数相加是否是素数
        if(TheSumOfOddAndEvenNumbers<=1){
            return false;
        }else {
            for (int j = 2; j < TheSumOfOddAndEvenNumbers; j++) {
                if( TheSumOfOddAndEvenNumbers % j == 0){
                    return false;
                }
            }
        }
        return true;
    }
}

方法二（利用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;
    }
}