描述

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

输入描述：

输入说明

1 输入一个正偶数n

2 输入n个整数

注意：数据可能有多组

输出描述：

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

示例：

输入：

2 5 6 13

3 6

输出：

解法

重点是

如何判断是素数？
如何判断偶数？
如何判断奇数？
采用二分图、匈牙利算法查找最优组合。

匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法（英语：primal-dual methods）。美国数学家哈罗德·库恩（英语：Harold Kuhn）于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。

匈牙利算法主要用于解决一些与二分图匹配有关的问题，所以我们先来了解一下二分图。

二分图

那什么是二分图呢？就是能分成两组，X,Y。其中，X上的点不能相互连通，只能连去Y中的点，同理，Y中的点不能相互连通，只能连去X中的点。这样，就叫做二分图。

下图是典型的二分图。

可以看到，在上面的二分图中，每条边的端点都分别处于点集X和Y中。匈牙利算法主要用来解决两个问题：求二分图的最大匹配数和最小点覆盖数。

最大匹配数

本题的“素数伴侣”本质就是用二分图的最大匹配数来求解。假设奇数是在X数组，偶数在Y数组，题目就转为了X能连上Y最多的组合。

为了能好的理解题意，我们把奇数当做是男生（Boys），偶数当做女生（Girls）：

Boys与Girls所有能配对的情况（奇数与偶数之和为素数），都用线连接起来了。于是题目变成了Boys与Girls能配对最多的方案。

现在我们来看看匈牙利算法是怎么运作的：

从B1看起，他可以与G2、G4配对，那就先暂时把他与G2连接。

接下来看B2，B2也可以配对G2，但由于这时G2已经与B1配对了，那怎么办呢？我们倒回去看G2目前被配对的B1，B1有没有别的选项呢？有G4，G4还没有被安排，那我们就给B1安排上G4。

然后观察B3，B3直接配上G1就好了，这没什么问题。至于B4，他只能配对G4，G4目前配的是B1。B1除了G4还可以选G2，但是呢，如果B1选了G2，G2的原配B2就没得选了。我们绕了一大圈，发现B4没有配对的机会了。

所以，最终的配对结果为B1G4、B2G2、B3G1。这也是Boys与Girls能配对最多的方案。

实现

 /*
  *  Copyright (c) waylau.com, 2022. All rights reserved.
 */
 
package com.waylau.nowcoder.exam.oj.huawei;

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

/**
 * 描述：若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，
 * 它们能应用于通信加密。现在密码学会请你设计一个程序，
 * 从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，
 * 挑选方案多种多样，例如有4个正整数：2，5，6，13，
 * 如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，
 * 能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
 * 输入描述：输入说明
 * 1 输入一个正偶数n
 * 2 输入n个整数
 * 注意：数据可能有多组
 * 输出描述：求得的“最佳方案”组成“素数伴侣”的对数。
 * 示例：
 * 输入：
 * 4
 * 2 5 6 13
 * 
 * 2
 * 3 6
 * 输出：
 * 2
 * 
 * 0
 *
 * @author <a href="https://waylau.com">Way Lau</a>
 * @since 2022-08-16
 */
public class HJ028PrimeCompanion {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 输入的数字先分好为奇数、偶数两组
        List<Integer> evenList= new ArrayList<>();
        List<Integer> oddList= new ArrayList<>();
        for (int i =0; i<n;i++) {
            int j = sc.nextInt();
            if (isEven(j)) {
                evenList.add(j);
            } else {
                oddList.add(j);
            }
        }
        
        int size = evenList.size();
        int count = 0;
        
        // 已经匹配的数的伴侣
        int[] evensMatch = new int[size];

        for (Integer odd : oddList) {
            // 用于标记对应的数是否查找过
            int[] used = new int[size];

            if (find(odd, evenList, used, evensMatch)) {
                count ++;
            }
        }
        
        // 输出
        System.out.println(count);
        
        // 关闭
        sc.close();
    }
    
    // 质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数
    // 0和1既不是质数也不是合数，最小的质数是2
    private static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        } else {
            for (int i = 2; i < n; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
        }

        return true;
    }

    // 偶数可以被2 整除的整数
    private static boolean isEven(int n) {
        if (n % 2 == 0) {
            return true;
        }

        return false;
    }
    
    /**
     * 找到指定数字的素数伴侣
     * 
     * @param odd
     * @param evens
     * @param used
     * @param evensMatch
     * @return
     */
    private static boolean find(int odd, List<Integer> evens, int[] used, int[] evensMatch) {
        // 遍历偶数：去检查当前传入的奇数能否与偶数哪些数匹配
        for (int i = 0; i < evens.size(); i++) {
            // 如果当前偶数与传入的奇数匹配，并且当前偶数位还没有匹配过奇数
            if (isPrime(odd + evens.get(i)) && used[i] == 0) {
                // 设置当前偶数位匹配为true，也就是 1
                used[i] = 1;
                
                // 如果第i个偶数没有伴侣
                // 或者第i个偶数原来有伴侣，并且该伴侣能够重新找到伴侣的话(这里有递归调用)
                // 则奇数odd可以设置为第i个偶数的伴侣
                // 这里采用了匈牙利算法，能让则让
                if (evensMatch[i] == 0 || find(evensMatch[i], evens, used, evensMatch)) {
                    evensMatch[i] = odd;
                    return true;
                }
            }
        }
        
        // 遍历完偶数都没有可以与传入奇数做伴侣的，该奇数只没有配对了
        return false;
    }

}

参考引用

本系列归档至https://github.com/waylau/nowcoder-exam-oj
《Java 数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action
《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html

Java题解 | HJ28 #素数伴侣#

描述

解法

匈牙利算法

二分图

最大匹配数

实现

参考引用