华为OD机试真题（Java），素数伴侣（100%通过+复盘思路）

在这里插入图片描述

一、题目描述

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

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

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

数据范围： 1≤n≤100，输入的数据大小满足 2≤val≤30000

二、输入描述

输入一个正偶数 n
输入 n 个整数

三、输出描述

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

四、解题思路

从输入中读取一个正偶数n；
创建一个长度为n的整数数组nums，用于存储n个整数；
循环读取n个整数，将其存储到nums数组中；
创建两个列表，一个用于存储偶数，一个用于存储奇数；遍历nums数组，将偶数存储到偶数列表（evens）中，将奇数存储到奇数列表（odds）中；
创建一个长度为偶数列表evens的整数数组evenMatch，用于存储每个偶数的伴侣奇数；初始化count为0，用于记录素数伴侣的对数；
对每个奇数进行匹配操作；遍历奇数列表odds，依次取出一个奇数odd；
- 创建一个布尔数组match，用于记录每个偶数是否已被占用；初始化为false；
- 使用递归函数find()进行偶数的匹配；在find()函数中，依次遍历偶数列表evens，取出一个偶数even；
  - 如果该偶数未被占用且偶数与奇数的和是素数（调用isPrime()函数判断），则将该奇数设置为偶数的伴侣，即evenMatch[i] = odd，并将该偶数设置为已占用（match[i] = true）；
  - 如果该偶数已被其他奇数占用，则递归调用find()函数，寻找其他可匹配的偶数；
- 如果能找到素数匹配，则count加1；
输出count，即最佳方案组成素数伴侣的对数；

五、Java算法源码

java">public static void main(String [] args){
    Scanner in = new Scanner(System.in);
    while(in.hasNext()){
        int n = in.nextInt();
        //定义数组
        int [] nums = new int[n];
        for(int i = 0;i < n ;i++){
            nums[i] = in.nextInt();
        }
        //分装为 偶数数组 和奇数数组
        List<Integer> evens = new ArrayList<>();
        List<Integer> odds = new ArrayList<>();

        for(int num:nums){
            if(num % 2 ==0){
                evens.add(num);
            }else{
                odds.add(num);
            }
        }
        //偶数的伴侣
        int [] evenMatch = new int[evens.size()];
        int count = 0;
        //用每个奇数 尝试匹配偶数
        for(int i = 0;i < odds.size();i++){
            int odd = odds.get(i);
            //偶数是否被占用
            boolean [] match = new boolean[evens.size()];
            if(find(odd,evens,evenMatch,match)){
                count++;
            }
        }
        System.out.println(count);

    }
}

private static boolean find(int odd,List<Integer> evens,int [] evenMatch,boolean [] match){
    for(int i = 0;i < evens.size();i++){
        int even = evens.get(i);
        //挨个匹配 偶数
        if(!match[i] && isPrime(even + odd)){
            //这个偶数没有被占用 且 偶数+奇数 为素数
            //增加访问标记
            match[i] = true;
            if(evenMatch[i] == 0 || find(evenMatch[i],evens,evenMatch,match)){
                //偶数索引对应的 素数为0 说明没有被其他素数占用 或者可以找到素数
                //则将该奇数设置为偶数的伴侣
                evenMatch[i] = odd;
                //找到了素数
                return true;
            }

        }
    }
    return false;
}


private static boolean isPrime(int x){
    if(x == 1){
        return false;
    }
    for(int i = 2; i <= (int)Math.sqrt(x);i++){
        if(x % i == 0){
            return false;
        }
    }
    return true;
}