素数伴侣

以你之姓@ 2023-06-29 10:40 18阅读 0赞

[https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e?tpId=37&tqId=21251&tPage=2&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking][https_www.nowcoder.com_practice_b9eae162e02f4f928eac37d7699b352e_tpId_37_tqId_21251_tPage_2_rp_ru_2Fta_2Fhuawei_qru_2Fta_2Fhuawei_2Fquestion-ranking]

## 一、问题描述 ##

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

输入:

有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为\[2,30000\]。

输出:

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

例如：

输入：

4
    2 5 6 13

输出：

## 二、代码实现 ##

采用匈牙利算法：

匈牙利算法是一种在多项式时间内求解任务**分配**问题的**组合**优化算法，其核心在于将数据看成一个无向图G=(V, E)，其中，顶点集V可以分割成两个互不相交的子集V1，V2。

判断一个图是不是二分图可以采用红蓝点的方法。首先，将任意一个顶点染成红色，再把这个点相邻的顶点染成蓝色，如果按照这种染色方式可以将所有的顶点全部着色，并且相邻的顶点颜色不同，那么该图就是一个二分图。

下面，我们将输入的偶数个元素分为奇数部分和偶数部分，那么两个元素之和想要成为素数，其必要条件就是为奇数（除了2之外偶数不可能是素数，问题中元素的取值范围为\[2, 30000\]），也就是说，两个元素必须一个是奇数一个是偶数。

import java.util.Scanner;
    import java.util.ArrayList;
    public class Main {
     
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
                String str = sc.nextLine();
                int N = Integer.parseInt(str);
                long[] nums = new long[N];
                String[] str1 = sc.nextLine().split(" ");
                for (int i = 0; i < N; i++) {
                    nums[i] = Integer.parseInt(str1[i]);
                }
                // 偶数部分
                ArrayList<Long> evens = new ArrayList<Long>();
                // 奇数部分
                ArrayList<Long> odds = new ArrayList<Long>();
                for (int i = 0; i < N; i++) {
                    if (nums[i] % 2 == 0) { // 偶数
                        evens.add(nums[i]);
                    } else { // 奇数
                        odds.add(nums[i]);
                    }
                }
                long[] evensMatch = new long[evens.size()];
                int result = 0;
                for (int i = 0; i < odds.size(); i++) {
                    int[] used = new int[evens.size()];
                    if (find(odds.get(i), evens, used, evensMatch)) {
                        result++;
                    }
                }
                System.out.println(result);
            }
            sc.close();
        }
    
        public static boolean find(long x, ArrayList<Long> evens, int[] used, long[] evensMatch) {
            int j;
            for (j = 0; j < evens.size(); j++) {
                if (isPrime(x + evens.get(j)) && used[j] == 0) {
                    //used[j]==0 表示还没有试图将evens.get(j)与一个奇数配对，于是可以试图配对
                    used[j] = 1;
                    if (evensMatch[j] == 0 || find(evensMatch[j], evens, used, evensMatch)) {
                        //试图配对，并且配对成功：1、之前试图配对但实际上没有配对成功；2、之前配对成功，但是可以换到其他可以配对的位置（可以腾出位置）
                        evensMatch[j] = x;
                        return true;
                    }
                }
            }
            return false;
        }
     
        private static boolean isPrime(long num) {
            if (num == 1) {
                return false;
            }
            for (int i = 2; i < Math.sqrt(num); i++) {
                if (num % i == 0) {
                    return false;
                }
            }
            return true;
        }
     
    }

参考：

[https://blog.csdn.net/dark\_scope/article/details/8880547][https_blog.csdn.net_dark_scope_article_details_8880547]

[https://blog.csdn.net/kevinjqy/article/details/54584114][https_blog.csdn.net_kevinjqy_article_details_54584114]

[https://baike.baidu.com/item/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95][https_baike.baidu.com_item_E5_8C_88_E7_89_99_E5_88_A9_E7_AE_97_E6_B3_95]

[https://www.cnblogs.com/shenben/p/5573788.html][https_www.cnblogs.com_shenben_p_5573788.html]

[https://zhuanlan.zhihu.com/p/62981901][https_zhuanlan.zhihu.com_p_62981901]

[https://www.wmathor.com/index.php/archives/1344/][https_www.wmathor.com_index.php_archives_1344]

[https_www.nowcoder.com_practice_b9eae162e02f4f928eac37d7699b352e_tpId_37_tqId_21251_tPage_2_rp_ru_2Fta_2Fhuawei_qru_2Fta_2Fhuawei_2Fquestion-ranking]: https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e?tpId=37&tqId=21251&tPage=2&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking
[https_blog.csdn.net_dark_scope_article_details_8880547]: https://blog.csdn.net/dark_scope/article/details/8880547
[https_blog.csdn.net_kevinjqy_article_details_54584114]: https://blog.csdn.net/kevinjqy/article/details/54584114
[https_baike.baidu.com_item_E5_8C_88_E7_89_99_E5_88_A9_E7_AE_97_E6_B3_95]: https://baike.baidu.com/item/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95
[https_www.cnblogs.com_shenben_p_5573788.html]: https://www.cnblogs.com/shenben/p/5573788.html
[https_zhuanlan.zhihu.com_p_62981901]: https://zhuanlan.zhihu.com/p/62981901
[https_www.wmathor.com_index.php_archives_1344]: https://www.wmathor.com/index.php/archives/1344/