题解 | #素数伴侣#

利用了一点贪心的思想，每次都找只有一对的，如果找不到就找两对的，依次类推，每找到一对就把这两个元素拿掉，直到没有一对素数对，此时返回结果

提交了五次才通过，要是真实面试，必定是寄了

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String str = scanner.nextLine();
        String[] strArr = str.split(" ");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(strArr[i]);
        }
        System.out.println(getMaxValue(arr));
    }

    public static int getMaxValue(int[] arr) {
        int n = 1;
        int res = 0;
        while (true) {
            boolean flag = true;
            boolean countFlag = true;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] < 0) {
                    continue;
                }
                int count = 0;
                int index = -1;
                for (int j = 0; j < arr.length; j++) {
                    if (i == j || arr[j] < 0) {
                        continue;
                    }
                    if (isSu(arr[i], arr[j])) {
                        flag = false;
                        index = j;
                        count ++;
                    }
                }
                if (count <= n && count > 0) {
                    n = 1;//只要有一个两对被组合的，就重新找只有一对组合的
                    countFlag = false;
                    arr[index] = -1;
                    arr[i] = -1;
                    res += 1;
                }
            }
            if (countFlag) { //如果没有找不到n对组合的，就把n+1
                n++;
            }
            if (flag) {
                return res;
            }
        }
    }

    public static boolean isSu(int a, int b) {
        int n = (int)Math.sqrt(a + b);
        for (int i = 2; i <= n; i++) {
            if ((a + b) % i == 0) {
                return false;
            }
        }
        return true;
    }

}