题解 | #素数伴侣#

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;
import java.util.stream.Collectors;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String nextLine = in.nextLine();
            if (Objects.isNull(nextLine) || nextLine.equals("")) {
                break;
            }
            int n = Integer.parseInt(nextLine);
            List<Integer> collect = Arrays.stream(in.nextLine()
                .split(" "))
                .map(Integer::parseInt)
                .collect(Collectors.toList());
            // 记录已计算的是否为质数：只能被1和它自身整除的数
            Map<Integer, Boolean> record = new HashMap<>();
            List<Cord> indexMap = new ArrayList<>();
            // 冒泡所有组合,将奇数放在右侧，偶数放在左侧，由于奇数+奇数=偶数，偶数+偶数=偶数，偶数不为素数（质数），所以这是完美的二分图匈牙利算法
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    if (valid(record, collect.get(i) + collect.get(j))) {
                        if (collect.get(i) % 2 == 0) {
                            indexMap.add(new Cord(i, j));
                        } else {
                            indexMap.add(new Cord(j, i));
                        }
                    }
                }
            }
            // 获取所有的x
            List<Integer> collect1 = indexMap.stream()
                .map(item -> item.getFrom())
                .distinct()
                .collect(Collectors.toList());
            // 获取所有的y
            List<Integer> collect2 = indexMap.stream()
                .map(item -> item.getTo())
                .distinct()
                .collect(Collectors.toList());
            Map<Integer, Integer> yxMap = new HashMap<>();
            // 记录Y是否被占用
            Map<Integer, Boolean> booleanyMap = new HashMap<>();

            // 遍历所有的x
            for (int i = 0; i < collect1.size(); i++) {
                // 记录x是否已经换过y
                Map<Integer, Boolean> booleanxMap = new HashMap<>();
                Integer x = collect1.get(i);
                dfs(yxMap, booleanyMap, booleanxMap, indexMap, x);
            }
            // System.out.println(indexMap);
            System.out.println(yxMap.size());
        }

    }

    //22
    // 20923 22855 2817 1447 29277 19736 20227 22422 24712 27054 27050 18272 5477 27174 13880 15730 7982 11464 27483 19563 5998 16163
    public static boolean dfs(Map<Integer, Integer> yxMap, Map<Integer, Boolean> booleanyMap,
        Map<Integer, Boolean> booleanxMap, List<Cord> indexMap, Integer x) {

        List<Integer> yList = indexMap.stream()
            .filter(item -> item.getFrom() == x)
            .map(item -> item.getTo())
            .collect(Collectors.toList());
        for (Integer y : yList) {
            if (Objects.isNull(booleanyMap.get(y))) {
                booleanyMap.put(y, true);
                yxMap.put(y, x);
                booleanxMap.put(x, true);
                return true;
            }
            // 这个lastX有可能是抢人的x
            Integer lastX = yxMap.get(y);
            // 逼上一个x去找别的y找不到就false
            if (Objects.isNull(booleanxMap.get(lastX))) {
                booleanxMap.put(lastX, true);
                // 如果上一个x能找到y，那就更新这个y给当前x
                if (dfs(yxMap, booleanyMap, booleanxMap, indexMap, lastX)) {
                    yxMap.put(y, x);
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean valid(Map<Integer, Boolean> record, Integer integer) {
        if (Objects.isNull(record.get(integer))) {
            for (int i = 2; i <= Math.sqrt(integer); i++) {
                if (integer % i == 0) {
                    record.put(integer, false);
                    return false;
                }
            }
            record.put(integer, true);
            return true;
        }
        return record.get(integer);
    }
}

class Cord {
    Integer from;

    Integer to;

    public Cord(Integer from, Integer to) {
        this.from = from;
        this.to = to;
    }

    @Override
    public String toString() {
        return "Cord{" + "from=" + from + ", to=" + to + '}';
    }

    public Integer getFrom() {
        return from;
    }

    public void setFrom(Integer from) {
        this.from = from;
    }

    public Integer getTo() {
        return to;
    }

    public void setTo(Integer to) {
        this.to = to;
    }
}