题解 | #素数伴侣#

def is_prime(n):
    """判断一个数是否为素数"""
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def find(x, used, match, evens, odds):
    """匈牙利算法的查找函数"""
    for i, even in enumerate(evens):
        # 如果和为素数且未使用过
        if is_prime(even + odds[x]) and not used[i]:
            used[i] = True
            # 如果当前偶数未匹配或者它的匹配可以找到新的配对
            if match[i] == -1 or find(match[i], used, match, evens, odds):
                match[i] = x
                return True
    return False

while True:
    try:
        # 读取输入
        n = int(input())
        nums = list(map(int, input().split()))
        
        # 分离奇数和偶数
        odds = [x for x in nums if x % 2 == 1]
        evens = [x for x in nums if x % 2 == 0]
        
        # 初始化匹配数组
        match = [-1] * len(evens)
        count = 0
        
        # 对每个奇数尝试匹配
        for i in range(len(odds)):
            used = [False] * len(evens)
            if find(i, used, match, evens, odds):
                count += 1
        
        print(count)
        
    except EOFError:
        break

#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

bool find(int x, vector<bool>& used, vector<int>& match, 
         const vector<int>& evens, const vector<int>& odds) {
    for (int i = 0; i < evens.size(); i++) {
        if (isPrime(evens[i] + odds[x]) && !used[i]) {
            used[i] = true;
            if (match[i] == -1 || find(match[i], used, match, evens, odds)) {
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        
        // 分离奇数和偶数
        vector<int> odds, evens;
        for (int num : nums) {
            if (num % 2) odds.push_back(num);
            else evens.push_back(num);
        }
        
        // 匈牙利算法求最大匹配
        vector<int> match(evens.size(), -1);
        int count = 0;
        
        for (int i = 0; i < odds.size(); i++) {
            vector<bool> used(evens.size(), false);
            if (find(i, used, match, evens, odds)) {
                count++;
            }
        }
        
        cout << count << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    private static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    private static boolean find(int x, boolean[] used, int[] match, 
                              List<Integer> evens, List<Integer> odds) {
        for (int i = 0; i < evens.size(); i++) {
            if (isPrime(evens.get(i) + odds.get(x)) && !used[i]) {
                used[i] = true;
                if (match[i] == -1 || find(match[i], used, match, evens, odds)) {
                    match[i] = x;
                    return true;
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            List<Integer> odds = new ArrayList<>();
            List<Integer> evens = new ArrayList<>();
            
            // 分离奇数和偶数
            for (int i = 0; i < n; i++) {
                int num = sc.nextInt();
                if (num % 2 == 1) odds.add(num);
                else evens.add(num);
            }
            
            // 匈牙利算法求最大匹配
            int[] match = new int[evens.size()];
            Arrays.fill(match, -1);
            int count = 0;
            
            for (int i = 0; i < odds.size(); i++) {
                boolean[] used = new boolean[evens.size()];
                if (find(i, used, match, evens, odds)) {
                    count++;
                }
            }
            
            System.out.println(count);
        }
    }
}