题解 | #素数伴侣#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.text.DateFormat;
import java.text.DecimalFormat;
import java.time.LocalDate;
import java.time.LocalDateTime;
import java.time.temporal.ChronoUnit;
import java.util.*;
import java.util.function.Function;
import java.util.function.IntFunction;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import static java.util.Arrays.*;
import static java.util.stream.Stream.*;


public class Main {
    public static void main(String[] args) throws IOException {

        testTh();
    }

    private static void testTh() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str;

        while ((str = bf.readLine()) != null) {
            str = bf.readLine();
            String[] s = str.split(" ");

            //odd 奇数
            //even 偶数
            ArrayList<Integer> number_odd = new ArrayList<>();
            ArrayList<Integer> number_even = new ArrayList<>();
            for (int i = 0; i < s.length; i++) {
                int parseInt = Integer.parseInt(s[i]);
                if (parseInt % 2 == 1) {
                    number_odd.add(parseInt);
                } else {
                    number_even.add(parseInt);
                }
            }
            int count = 0;
            int[] evenPair = new int[number_even.size()];
            for (int i = 0; i < number_odd.size(); i++) {
                boolean[] used = new boolean[number_even.size()];
                if (findPair(i, number_odd, number_even, evenPair, used)) {
                    count++;
                }
            }

            System.out.println(count);
        }


    }
    public  static Boolean findPair(Integer oddIndex, ArrayList<Integer> oddAL,
                                    ArrayList<Integer> evenAL, int[] evenPair, boolean[] used) {
        for (int i = 0; i < evenAL.size(); i++) {
            if (!used[i] && testPrime(oddAL.get(oddIndex) + evenAL.get(i))) {
                used[i] = true;
                if (evenPair[i] == 0 ||
                        findPair(evenPair[i] - 1, oddAL, evenAL, evenPair, used)) {
                    evenPair[i] = oddIndex + 1;
                    return true;
                }
            }
        }

        return false;
    }
    public static Boolean testPrime(Integer num) {
        if (num <= 3) {
            return num > 1;
        }
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }

        double sqrt = Math.sqrt(num);
        for (int i = 5; i < sqrt; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

}