题解 | #素数伴侣#线性筛质数+二分图最大匹配

1. 首先，使用线性筛质数，将60000以内的质数全部求出；
2. 可以看出两个数的和组成一个质数，那么这两个数必然一个是奇数，另一个是偶数，所以可以将奇数和偶数分成两个集合。使用匈牙利算法求解这两个集合的最大匹配。

import java.util.*;

public class Main {
    
    static int[] primes = new int[60010];
    static boolean[] st = new boolean[60010];
    static int cnt = 0;
    
    static List<Integer>[] g;
    static boolean[] stt;
    static int[] match;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        get_primes();
        Set<Integer> set = new HashSet<>();
        for(int x: primes) {
            set.add(x);
        }
        while(sc.hasNext()) {
            int n = sc.nextInt();
            List<Integer> odd = new ArrayList<>();
            List<Integer> even = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                int x = sc.nextInt();
                if(x % 2 == 0) {
                    even.add(x);
                } else {
                    odd.add(x);
                }
            }
            int m = odd.size();
            g = new List[m];
            for(int i = 0; i < m; i++) {
                g[i] = new ArrayList<>();
            }
            for(int i = 0; i < m;i++) {
                for(int j = 0; j < even.size(); j++) {
                    if(set.contains(odd.get(i)+even.get(j))) {
//                         System.out.println(i + " " + j);
                        g[i].add(j);
                    }
                }
            }
            int res = 0;
            stt = new boolean[even.size()];
            match = new int[even.size()];
            Arrays.fill(match, -1);
            for(int i = 0; i < m ;i++) {
                Arrays.fill(stt,false);
                if(find(i)) {
                    res++;
                }
            }
            System.out.println(res);
        }
    }
    
    static void get_primes() {
        for(int i = 2; i <= 60005; i++) {
            if(!st[i]) {
                primes[cnt++] = i;
            }
            for(int j = 0; primes[j] <= 60005 / i; j++) {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) {
                    break;
                }
            }
        }
    }
    
    static boolean find(int u) {
        for(int x : g[u]) {
            if(!stt[x]) {
                stt[x] = true;
                if(match[x] == -1 || find(match[x])) {
                    match[x] = u;
                    return true;
                }
            }
        }
        return false;
    }
}