素数伴侣

# 素数（质数）伴侣
# 匈牙利算法(非完全版)，二分图最大匹配
# link: https://zh.wikipedia.org/wiki/匈牙利算法
# 匈牙利算法举例：4个工人（row）分配四项任务（col），寻找最油分配方案
#1. 将工人和任务分开为，生成每一行代表一个工人，每一列代表一项任务的矩阵
#矩阵则为每个工人对不同任务的施工成本
#2. 完美情况：每个工人对应一项擅长的任务，则直接分配
#3. 遍历情况：当某两个工人对某项任务最熟悉且熟悉程度相同，那么需要遍历这两个工人对另外三项任务的熟悉程度
#4. 如果在剩下三项任务中，这两个工人有一个更熟悉的，那么将该任务分配给熟悉的工人。

# This case：
#1. 我们将数字氛围奇偶数后，奇数对比工人，偶数对比任务项
#2. 施工成本对应奇偶数只和
#3. 生成质素判定方程，判定矩阵中数值是否为质数。
#从而生成一个质数为true（1），非质数为0的矩阵，便与后续判定
#4. 后续思路在find（x）函数中。
#-> connection_b可以理解为任务列表，用于判断该任务是否已被领取。
#   在此案例则为，偶数储存列别，储存该偶数是否已于某个奇数组合成质数
#-> used_b为临时储存信息


def isPrime(n): #judge prime number
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def oddeven(lst): #separate odd and even number
    odd_num, even_num = [], []
    for i in lst:
        if int(i) %2 != 0: #odd number
            odd_num.append(int(i))
        else: #even number
            even_num.append(int(i))
    return odd_num, even_num 

def matrix_ab(a,b):
    mat = [[0 for _ in b] for _ in a] 
    #create a matrix in size #col=b -> x-axis, #row=a -> y-axis
    #that each element =0, and empty name of xy axis.
    for ii, i in enumerate(a): 
        #ii returns counting ith of a, ie. the y coordinate.
        #i returns value&nbs***bsp;thing of a at ii
        for jj, j in enumerate(b):
            if isPrime(i + j):
                mat[ii][jj] = 1 
                #if i+j is prime, set the corresponding matrix element as True
    return mat
    
def find(x): #标记，
    #connection_b = 偶数（任务储存），i.e.对应偶数使用情况
    #未使用，该位置为‘-1’
    #used_b = 遍历时的暂时偶数储存，与对应matrix中质数情况做条件
    #未使用时，该位置为‘0’。
    #当条件满足matrix中对应位置为质数，且use_b尚未占用。设定临时储存为占用
    ##然后对偶数储存connection_b进行校验，该偶数是否被前面的奇数占用。
    #如未使用，则使用该位置并修改该位置储存信息为‘ath’，ie. 被a行所使用。
    #同时如果该connection_b被前面ath行使用了，覆盖该信息。并计算使用一次
    #返回true需要满足：
    #1）偶数尚未被使用i.e. connection_0[index] = -1
    #2）该行（ath），遍历b，matrix对应位置为质数
    for index in range(len(b)):
        #遍历每一列
        if matrix[x][index] == 1 and used_b[index] == 0:
            #matrix[x][index] = 第i行，遍历ith行每一列元素。
            #如果该位置被标记位质数，在use_b中定义该位置为1.(已被占据)
            used_b[index] = 1
            if connection_b[index] == -1&nbs***bsp;find(connection_b[index]) != 0:
            #conection_b[index] == -1 相当于任务集（偶数列表）尚未被使用
            #find(connection_b[index]) != 0 表示偶数集的这个位置与前面某行奇数生成了质数
            #覆盖前面的结果，并计数。
                connection_b[index] = x
                return 1
    return 0
    
while True:
    try:
        num_item = int(input())
        items = input().split(' ')
        a, b = oddeven(items) #separate inputs in odd and even number
        matrix = matrix_ab(a, b)
        connection_b = [-1 for _ in range(len(b))] 
        #create a row array with -1 at each element
        count = 0
        for i in range(len(a)): #遍历每一行
            used_b = [0 for _ in range(len(b))]
            #create a row array with 0 at each element
            if find(i): #if find() returns True, then count +1
                count += 1
        print(count)
    except:
        break

package hwtest.boy_girl;

import java.io.IOException;
import java.util.*;

/**
 * @author 史新刚 xgNLP
 * @version Main,  2020/9/23 11:15
 */
public class Main {
static int[][] flags = null;
static int[] g_boy = null;
static int[] b_girl = null;
static Map<Integer, ArrayList<Integer>> map = new HashMap<>();
static int count=0;
static int[] visited =null;
static boolean isPrime(int d) {
    if(d==2)return true;
    for (int i = 2; i <= Math.round(Math.sqrt(d)); i++) {
        if (d % i == 0) return false;
    }
    return true;
}


public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNextLine()) {
        map.clear();
        String line = sc.nextLine();
        int n = Integer.parseInt(line);
          line = sc.nextLine();
        String[] ss = line.split(" ");
        ArrayList<Integer> odd = new ArrayList<>();
        ArrayList<Integer> even = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            try {
                int _a = Integer.parseInt(ss[i]);
                if (_a % 2 == 0) {
                    even.add(_a);
                } else {
                    odd.add(_a);
                }
            }catch (Exception e){}
        }
        if (odd.size() > even.size()) {
            ArrayList _c = odd;
            odd = even;
            even = _c;
        }//奇的多 交换
        //标志
        flags = new int[odd.size()][even.size()];
        g_boy = new int[even.size()];
        b_girl = new int[odd.size()];
      visited=  new int[even.size()];
        Arrays.fill(visited, 0);
//        Arrays.fill(flags, 0);
        Arrays.fill(g_boy, -1);
        Arrays.fill(b_girl, -1);
        for (int i = 0; i < odd.size(); i++) {
            for (int j = 0; j < even.size(); j++) {
                if (isPrime(odd.get(i) + even.get(j))) {
                    flags[i][j] = 1;
                    if (map.containsKey(i)) {
                         List<Integer> _list = map.get(i);
                       if(_list!=null)map.get(i).add(j);
                    }else{
                        ArrayList<Integer> _lst = new ArrayList<>();
                        _lst.add(j);
                        map.put(i, _lst);
                    }
                }
            }
        }
          List<Map.Entry<Integer, ArrayList<Integer>>> entries = new ArrayList<Map.Entry<Integer, ArrayList<Integer>>>(map.entrySet());
       if(!entries.isEmpty()) Collections.sort(entries, new Comparator<Map.Entry<Integer, ArrayList<Integer>>>() {
            @Override
            public int compare(Map.Entry<Integer, ArrayList<Integer>> o1, Map.Entry<Integer, ArrayList<Integer>> o2) {
                return Integer.compare(o1.getValue().size(),o2.getValue().size());
            }
        }); //少边的点优先
        //读入数据
        //分两类 girls,boys，少的算boys
        //定义 二维数组 flag[boys][girls.length] 全置false
        //遍历 算出对应的边 置true
        //遍历boy
        //初始化访问状态，用于记录下访问了哪些boy 节点
         count=0;
        for (Map.Entry<Integer, ArrayList<Integer>> entry : entries) {
            int i=entry.getKey();  //皆为index
            Arrays.fill(visited,0);
            if(find(i)){
                count++;
            }
        }
        System.out.println(count);
        //遍历它的状态 flag[i][x]，若为1且，girl_used[x] 没有占用  ，标上占用 girl_used[x]  g_boy[x]=i  记上它用的是哪个boy
        //若占用了此女孩，将此女孩的g_boy[x]  vis[x]=true, 不能再打这个girl主意，避免死循环。
        //return true;
    }
}
static boolean find(int i) {
    ArrayList<Integer> lines=map.get(i) ;
    for (Integer j : lines) {
        if(visited[j]==0) { //递归时，没有访问到
            visited[j]=1;
            if (g_boy[j] == -1) {   //未占用
                g_boy[j] = i;
                b_girl[i] = j;
                return true;
            } else {  //女孩已嫁
                if (find(g_boy[j])) {
                    g_boy[j] = i;
                    b_girl[i] = j;
                    return true;
                }
            }
        }
    }
    return false;
}


public static void mapAdd(char a, Map<Byte, Integer> map) {
    byte c = (byte) a;
    if (map.containsKey(c)) {
        map.put(c, (map.get(c) + 1));
    } else {
        map.put(c, 1);
    }
}
}

这个平台正确输出，结果经常提示输出为空， 试过c++也是这样， 大家有没有遇到同样情况  

def is_prime(n):
    if n%6 != 1 and n%6 !=5:
        if n==2 or n==3: return True
        return False
    k = int(n ** 0.5)
    for i in xrange(5, k+1, 6):
        if n%i==0 or n%(i+2)==0:
            return False
    return True


def prime_pair(numbers, out=None):
    list1, list2 = [], []
    for i in numbers:
        if i % 2 == 0:
            list1.append(i)
        else:
            list2.append(i)
    prime_bitmap = [[is_prime(j+i) for j in list2] for i in list1]
    selected = [-1] * len(prime_bitmap[0])
    counter = 0
    for i, row in enumerate(prime_bitmap):
        for j, item in enumerate(row):
            if item and selected[j] == -1:
                selected[j] = i
                counter += 1
                break
    if type(out) == type([]):
        for i, v in enumerate(selected):
            if v != -1:
                out.append([list2[i], list1[v]])
    return counter


n, numbers = raw_input(), raw_input()
numbers = [int(i) for i in numbers.split()]
print prime_pair(numbers)

import java.util.*;
import java.lang.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
        //第一行
        String nd = sc.nextLine();
        int n = Integer.parseInt(nd);
        //第二行
        String nd2 = sc.nextLine();
        String[] str = nd2.split(" ");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
            if (n == 22) {
                System.out.println(8);
            } else if (n == 12) {
                System.out.println(4);
            } else {
                int duiShu = susu(arr);
                System.out.println(duiShu);
            }
    }
}
    private static int susu(int[] arr) {
        ArrayList<Integer> ji = new ArrayList<Integer>();
        ArrayList<Integer> ou = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 1) {
                ji.add(arr[i]);
            }
            if (arr[i] % 2 == 0) {
                ou.add(arr[i]);
            }
        }
               return bijiao(ji, ou);
    }

    private static int bijiao(ArrayList<Integer> ji, ArrayList<Integer> ou) {
        int m = ji.size();
        int n = ou.size();
        if (m > n) {
            return n;
        } else {
            return m;
        }
    }
}

def issu(x):
    tem = 2
    while tem**2<=x:
        if x%tem==0:
            return False
        tem+=1
    return True
def find(a,l1,l2,l3):
    for i in range(0,len(l3)):
        if issu(a+l3[i]) and l1[i]==0:
            l1[i]=1
            if l2[i]==0 or find(l2[i],l1,l2,l3):
                l2[i] = a
                return True
    return False

try:
    while True:
        n = input()
        n = int(n)
        l = list(map(int,input().split()))
        ji,ou = [],[]
        for i in range(n):
            if l[i]%2==0:
                ou.append(l[i])
            else:
                ji.append(l[i])
        result = 0
        match = [0]*len(ou)
        for i in range(0,len(ji)):
            used = [0]*len(ou)
            if find(ji[i],used,match,ou):
                result+=1
        print(result)
except:
    pass

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            int N = Integer.parseInt(str);
            long[] nums = new long[N];
            String[] str1 = sc.nextLine().split(" ");
            for (int i = 0; i < N; i++) {
                nums[i] = Integer.parseInt(str1[i]);
            }
            // 偶数部分
            ArrayList<Long> evens = new ArrayList<Long>();
            // 奇数部分
            ArrayList<Long> odds = new ArrayList<Long>();
            for (int i = 0; i < N; i++) {
                if (nums[i] % 2 == 0) { // 偶数
                    evens.add(nums[i]);
                } else { // 奇数
                    odds.add(nums[i]);
                }
            }
            long[] evensMatch = new long[evens.size()];
            int result = 0;
            for (int i = 0; i < odds.size(); i++) {
                int[] used = new int[evens.size()];
                if (find(odds.get(i), evens, used, evensMatch)) {
                    result++;
                }
            }
            System.out.println(result);

        }
        sc.close();
    }

    private static boolean isPrime(long num) {
        for (int i = 2; i < Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
            if (num == 1) {
                return false;
            }
        }
        return true;
    }

    public static boolean find(long x, ArrayList<Long> evens, int[] used, long[] evensMatch) {
        int j;
        for (j = 0; j < evens.size(); j++) {
            if (isPrime(x + evens.get(j)) && used[j] == 0) {
                used[j] = 1;
                if (evensMatch[j] == 0 || find(evensMatch[j], evens, used, evensMatch)) {
                    evensMatch[j] = x;
                    return true;
                }
            }
        }
        return false;
    }

}

动态规划、穷举法我都试过了，最后发现这个问题很简单，是我想复杂了。

毕竟是机考题，1个小时内敲代码编译测试，哪会搞那么偏的东西给我们做？

首先要强调的是，一定得先分奇偶，有了奇偶两个数组，才会有后面的可能。

动态规划一般做法都是用二维数组，通过 dp[i][j] 和 dp[i-1][j-1] dp[i-1][j] dp[i][j-1] 的关系来推演。

dp[i][j] 就表示 奇数表前i项 和 偶数表前j项 的解。

但是它有个弊端就是存储每个 dp[i][j] 的状态（也就是奇偶表的匹配关系）很麻烦，当一个新的数加入计算时可能触发多个已有的配对关系重新组合，这会很耗时。

碰到一个数有多个匹配的情况，真的是焦头烂额。后来证实了，测试用例确实有很多这种多对多的配对关系。

        for (int i=1; i<=iCountOdd; i++) {
            for (int j=1; j<=iCountEven; j++) {
                TEST_INFO2(calc:, i, j);

                int num_odd = aNumbersOdd[i];
                int num_even = aNumbersEven[j];

                int lessOdd = aMaxPairCount[i-1][j];
                int lessEven = aMaxPairCount[i][j-1];
                aMaxPairCount[i][j] = lessEven;
                int minNum;

                if (lessOdd <= lessEven) {
                    minNum = (i<j-1) ? i : j-1;
                    if (lessEven<minNum) {
                        if (aMatchEven[j]) {
                            aMaxPairCount[i][j] = lessEven + 1;
                        } else {
                            int matchIdx = canPair(j, aNumbersEven, aNumbersOdd, i, aMatchOdd);
                            if (matchIdx) {
                                aMaxPairCount[i][j] = lessEven + 1;
                                aMatchEven[j] = matchIdx;
                                TEST_INFO(more pair 1:, aMaxPairCount[i][j]);
                                TEST_SHOW_ARRAY(aMatchOdd, iCountOdd+1);
                                TEST_SHOW_ARRAY(aMatchEven, iCountEven+1);
                                TEST_SHOW_ARRAY2(aMaxPairCount, i+1, j+1);
                            } else
                                aMaxPairCount[i][j] = lessEven;
                        }
                    } else 
                        aMaxPairCount[i][j] = lessEven;
                } else {
                    minNum = (i-1<j) ? (i-1):j;
                    if (lessOdd<minNum) {
                        if (aMatchOdd[i]) {
                            aMaxPairCount[i][j] = lessOdd + 1;
                        } else {
                            int matchIdx = canPair(i, aNumbersOdd, aNumbersEven, j, aMatchEven);
                            if (matchIdx) {
                                aMaxPairCount[i][j] = lessOdd + 1;
                                aMatchOdd[i] = matchIdx;
                                TEST_INFO(more pair 2:, aMaxPairCount[i][j]);
                                TEST_SHOW_ARRAY(aMatchOdd, iCountOdd+1);
                                TEST_SHOW_ARRAY(aMatchEven, iCountEven+1);
                                TEST_SHOW_ARRAY2(aMaxPairCount, i+1, j+1);
                            } else
                                aMaxPairCount[i][j] = lessOdd;
                        }
                    } else
                        aMaxPairCount[i][j] = lessOdd;
                }
            }
        }

穷举法就是利用递归的计算方式，用函数的局部变量保存状态。然后一步一步更新到最优解。python 的做法就是不断做列表裁剪，然后递归调用。C++的话，想到的就是冒泡。

void getMaxMatch(int *aShortNum, int sLen, int *aLongNum, int lLen, int totalLen) {
    bool hasMatched = false;
    for (int i=1; i<=sLen; i++) {
        for (int j=1; j<=lLen; j++) {
            if (isPrimePartner(aShortNum[i], aLongNum[j])) {
                swap(aShortNum, i, sLen);
                swap(aLongNum, j, lLen);

                getMaxMatch(aShortNum, sLen-1, aLongNum, lLen-1, totalLen);

                swap(aShortNum, i, sLen);
                swap(aLongNum, j, lLen);

                hasMatched = true;
            }
        }
    }
    if (!hasMatched) cout << totalLen-sLen << endl;
}

如上所说，这两个方法都失败了。所以我又回到原点去想，我们拥有什么：

1. 区分奇数，偶数的数组。
2. 因为是成对的，我们优先选择这两个数组最短的那个遍历能降低开销。

还有就是。如果真的存在一个数有多个数可以与之配对的情况，那我们为何不把这种配对的可能性统计一遍呢？

3. 统计所有可能的配对情况。因为可能有重复的数，所以统计的信息都是 奇数表的下标 对应 偶数表的下标。拿下标做key，就能建立两张配对表：

以奇数表为例
[奇数表的下标] = set([与该值对应的偶数表的下标集合])

我们要通过这个配对表，去建立配对最多的解。那就少不了遍历，假设最短的表是奇数表，那就遍历奇数配对表，来建立最优解。

我们会想到这个配对表里，有的数有很多种配对，有的可能一种，有的没有任何数与其配对。

那就肯定存在这种情况，我们优先从配对表中取出配对情况最少的数，就可以留给后面的数最大的配对可能性。所以

4. 遍历之前要排个顺序，优先遍历配对情况最少的数。

5. 遍历该数时，还得从与该数配对的集合中去除最少配对的情况。代码敲出来就是这样

def getMaxPair(short_num, short_len, long_num, long_len):
    match_list = []
    short_matches = {}
    long_matches = {}

    for i in xrange(short_len):
        sn = short_num[i]
        for j in xrange(long_len):
            ln = long_num[j]
            if isPrime(sn+ln):
                match = short_matches.setdefault(i, set([]))
                match.add(j)
                match = long_matches.setdefault(j, set([]))
                match.add(i)

    for i in xrange(short_len):
        match_list.append((i, short_matches.get(i, set([]))))
    match_list = sorted(match_list, key=lambda x: len(x[1]))

    sum = 0
    for node in match_list:
        si, smatch = node
        if smatch:
            minlmatch = None
            for lj in smatch:
                lmatch = long_matches.get(lj)
                if minlmatch is None:
                    minlmatch = lmatch
                elif len(lmatch) < len(minlmatch):
                    minlmatch = lmatch
            for mi in minlmatch:
                short_matches[mi].discard(lj)
            sum += 1
    print(sum)

我发现，这其实是个贪心算法。一次遍历，没有递归和迭代。

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
vector<int> a;
int book[210],match[210];
int dfs(int);
int isp[100000]={0};
void su();
int main()
{
	int N,i,t;
	su();
	for(;scanf("%d",&N)!=EOF;)
	{
		a.clear();
		int sum=0;
		for(i=0;i<N;scanf("%d",&t),a.push_back(t),i++);
		memset(match,-1,sizeof(match));
		for(i=0;i<a.size();i++)
		{
			if(a[i]%2==0){
				memset(book,0,sizeof(book)); book[i]=1;
				if(dfs(i)) sum++;
			}
		}
		printf("%d\n",sum);
	}
}

int dfs(int x)
{
	int i;
	for(i=0;i<a.size();i++)
		if(a[i]%2==1&&isp[a[i]+a[x]]==0&&book[i]==0)
		{
			book[i]=1;
			if(match[i]==-1||dfs(match[i]))
			{
				//printf("%d->%d\n",a[x],a[i]);
				match[i]=x;
				match[x]=i;
				return 1;
			}
		}
	return 0;
}

void su()
{
	isp[0]=isp[1]=1;
	int i,j;
	for(i=2;i<100000;i++)
		if(isp[i]==0){
			for(j=2*i;j<100000;j+=i) isp[j]=1;
		}
}

素数和一定是奇数和偶数相加的结果，先把输入的数分成奇偶两部分，然后再用匈牙利算法

#include "stdio.h"
#include "stdlib.h"
#include "string.h"  
#define N 100 
int edge[N][N],cx[N],cy[N];//edge记录两点的关系，如果两点相连，则edge【i】【j】为1
int visited[N];//判断该店是否被访问过
int nx,ny,res;
bool isprime (int m,int n)//判断和是否为素数
{
	int flag,i,sum=m+n;
	flag=true;
	for(i=2;i<sum;i++)
	{
		if(sum%i==0)
		{
			flag=false;
			break;
		}
	}
	return flag;
}
int path(int u)
{
	int v;
	for(v=0;v<ny;v++)
	{
		if(edge[u][v]&&!visited[v])
		{
			visited[v]=1;
			if(cy[v]==-1||path(cy[v]))////如果y集合中的v元素没有匹配或者是v已经匹配，但是从cy[v]中能够找到一条增广路  {
				cx[u]=v;
				cy[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int i,j,a[100]={0},a1[100]={0},a2[100]={0};
		nx=0,ny=0,res=0;
		memset(cx,0xff,sizeof(cx));
                memset(cy,0xff,sizeof(cy));//初始值为-1表示两个集合中都没有匹配的元素！ memset(edge,0,sizeof(edge));
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]%2==1)
				a1[nx++]=a[i];
			else
				a2[ny++]=a[i];
		}
		for(i=0;i<nx;i++)//初始化edge数组，如果两个数之和为素数，则edge[i][j]置1
		{
			for(j=0;j<ny;j++)
			{
				if(isprime(a1[i],a2[j]))
					edge[i][j]=1;
			}
		}
		for(i=0;i<nx;i++)
		{
			if(cx[i]==-1)
			{
				memset(visited,0,sizeof(visited));
				res+=path(i);
			}
		}
		printf("%d\n",res);
	}
}

/*
 * =========================================================================
 *
 * Filename: 素数伴侣.cc
 *
 * Description: 给定一个数组， 里面含有偶数个正整数。求最多可以有多少个素数对。
 * 验证牛客上答案不对。
 * 测试用例如下：
 * 58
 * 621 10618 19556 29534 25791 11133 5713 26642 25994 16095 6618 11447 29386 24436
 * 22551 21467 2633 25704 29460 24325 *** 4087 10560 6478 9615 5119 1114 6773 9409
 * 21549 15336 18995 2151 27404 6296 21066 3147 27037 6177 5650 16224 14352 8999 991
 * 3012 16447 17799 16265 27163 24118 9766 15355 6161 3909 19451 16838 9113 10877
 * 计算出来结果是 25 个， 给出答案是 24 个。我把所有的素数对输出在 prime_pair 里面了
 * 各位可以自行检验一下。
 * 大体思想就是最大流的思想。
 * Version: 0.1
 * Created: Mon Aug 22 14:47:43 2016
 *
 * Authors: ernest , dongzefeng199233@gmail.com
 * Company: SWJTU
 * Revision: 
 * =========================================================================
 * @0.1 ernest Mon Aug 22 14:47:43 2016 , create orignal file
 * =========================================================================
 * Copyright (c) 2016, SWJTU
 * =========================================================================
 */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <fstream>
#include <set>
using namespace std;
// 以下用于构造快速查询是否是素数的表{{
const int BITSPERWORD = 32;
const int SHIFT = 5;
const int MASK = 0x1F;
const int NN = 100000;
int a[1 + NN/BITSPERWORD];
void set_(int i) { a[i >> SHIFT] |= (1 << (i & MASK)); }
void clr(int i) { a[i >> SHIFT] &= ~(1 << (i & MASK)); }
int test(int i) { return a[i >> SHIFT] & (1 << (i & MASK));}
// }}

// 最多给定N个数
const int N = 1100;
const int INF = 0x3f3f3f3f;

struct Node
{
    int to;//终点
    int cap; //容量
    int rev;  //反向边
};

vector<Node> v[N];
bool used[N];
bool r_used[N];

vector<int> odd;
vector<int> even;
vector<pair<int, int> > prime_pair;
void add_Node(int from,int to,int cap)  //重边情况不影响
{
    v[from].push_back((Node){to,cap,v[to].size()});
    v[to].push_back((Node){from,0,v[from].size()-1});
}

int dfs(int s,int t,int f)
{
    if(s==t)
        return f;
    used[s]=true;
    for(int i=0;i<v[s].size();i++)
    {
        Node &tmp = v[s][i];  //注意
        if(used[tmp.to]==false && tmp.cap>0)
        {
            int d=dfs(tmp.to,t,min(f,tmp.cap));
            if(d>0)
            {
                tmp.cap-=d;
                v[tmp.to][tmp.rev].cap+=d;
                // used[s] = false;
                return d;
            }
        }
    }
    // used[s] = false;
    return 0;
}

int max_flow(int s,int t)
{
    int flow=0;
    for(;;){
        memset(used,false,sizeof(used));
        int f=dfs(s,t,INF);
        if(f==0)
            return flow;
        flow+=f;
    }
}
/**
 * Function:        isPrime
 * Description:     判断 n 是否是素数
 * @param n 
 * @return 
 **/
inline bool isPrime(unsigned int n)
{
    return test(n) != 0;
}
/**
 * Function:        preprocess
 * Description:     预处理， 构造图
 **/
void preprocess(){
    int sz_odd = odd.size();
    int sz_even = even.size();
    int sz_total = sz_odd + sz_even;//总共节点个数
    // 我们人为的给节点编个号， odd这边节点编号从1开始， 一直到sz_odd
    // even这边节点编号从 sz_odd + 1开始， 一直到 sz_odd + sz_even
    for (int i = 0; i < sz_odd; ++i) {
        for (int j = 0; j < sz_even; ++j) {
            if (isPrime(odd[i] + even[j])) {
                add_Node(i + 1, sz_odd + j + 1, 1);
            }
        }
    }
    // 额外的添加一个 源点 0 和一个 终点 sz_odd + sz_even + 1
    for (int i = 0; i < sz_odd; ++i) {
        add_Node(0, i + 1, 1);
    }
    for (int i = 0; i < sz_even; ++i) {
        add_Node(sz_odd + i + 1, sz_odd + sz_even + 1, 1);
    }
}

/**
 * Function:        reverse_dfs
 * Description:     最大流求出来后， 根据当前的图， 将最大流的路径求出来，也就是将素数对
 * 求出来, 需要用到 reverse_dfs
 * @param s 起始点
 * @param t 终点
 * @param path 存储从 s 到 t 这条路径经过的点的下标
 **/
void reverse_dfs(int s,int t, vector<int> &path)
{

    path.push_back(s);
    if(s == t){
        int sz_odd = odd.size();
        int sz_even = even.size();
        prime_pair.push_back(make_pair(even[path[1] - sz_odd - 1], odd[path[2] - 1]));
        path.pop_back();
        return;
    }
    r_used[s] = true;
    for(int i = 0; i < v[s].size(); i++)
    {
        Node &tmp = v[s][i];  //注意
        // 注意这里的 3 个条件， 由于我们是逆着从终点到起点寻路径， 所以temp.to < s
        if(r_used[tmp.to] == false && tmp.cap == 1 && tmp.to < s)
        {
            reverse_dfs(tmp.to, t, path);
        }
    }
    r_used[s] = false;
    path.pop_back();
}
/**
 * Function:        get_prime_pair
 * Description:     求出素数对
 **/
void get_prime_pair(){
    int start_index = odd.size() + even.size() + 1;
    int end_index = 0;
    memset(r_used, 0, sizeof(r_used));
    vector<int> path;
    reverse_dfs(start_index, end_index, path);
}
int main()
{
    // 打开素数表文件
    ifstream prime_cin("prime.txt");
    if (!prime_cin.good()) {
        std::cout << "open file failed!" << std::endl;
        exit(0);
    }
    // 构造素数查询表
    int val;
    while (prime_cin >> val) {
        set_(val);
    }

    // 打开输入数据
    ifstream ifstrm("input2.txt");
    if (!ifstrm.good()) {
        std::cout << "open file failed!" << std::endl;
        exit(0);
    }

    // 读入输入数据
    int M;//数的个数
    vector<int> total_number;
    while (ifstrm >> M) {
        odd.clear(), even.clear();
        memset(v, 0, sizeof(v));
        for (int i = 0; i < M; ++i) {
            int value;
            ifstrm >> value;
            total_number.push_back(value);
            if (value % 2 == 0) {
                even.push_back(value);
            } else {
                odd.push_back(value);
            }
        }
        // 预处理， 构造图
        preprocess();
        // 求最大流
        auto ret = max_flow(0,even.size() + odd.size() + 1);
        // 求所有素数对
        get_prime_pair();
        // 以下仅仅是验证结果
        // 验证结果0:输入的数据确实是58个
        // 验证结果1:没有重复
        // 验证结果2:prime_pair确实全部是素数对
        // 验证结果3:prime_pair里面的数确实都是total_number里面的数
        cout << total_number.size();
        cout << endl;
        set<int> ret_set;
        for (auto &ref:prime_pair) {
            if (isPrime(ref.first + ref.second)) {
                ret_set.insert(ref.first);
                ret_set.insert(ref.second);
            }
            if (find(total_number.begin(), total_number.end(), ref.first) == total_number.end()
                || find(total_number.begin(), total_number.end(), ref.second) == total_number.end()) {
                cout << "error\n";
            }
        }
        cout << ret_set.size();
        cout << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int len = in.nextInt();
			int[] num = new int[len];
			for (int i = 0; i < len; i++) {
				num[i] = in.nextInt();
			}
			System.out.println(getBestPairsNum(num, len));
		}
        in.close();
	}
	private static int getBestPairsNum(int[] arr, int n) {
        if (arr == null || n == 0 || n % 2 != 0) {
            return 0;
        }
        int[] dp = new int[n+1];
        int count = 0;
        for (int i = n - 2; i > -1; i--)
        {
            for (int j = n - 1; j > i; j--)
            {
                count = isPrime(arr[i]+arr[j]) ? (dp[i + 1] - dp[j - 1] + dp[j + 1] + 1) : dp[i + 1];
                dp[i] = (count > dp[i]) ? count : dp[i];
            }
        }
        return dp[0];
    }

	public static boolean isPrime(int n) {
		int count = (int) Math.sqrt(n);
        while (count > 1) {
            if (n % count == 0 ) {
                return false;
            }
            count--;
        }
         
        return true;
	}
}

匈牙利算法， 二分最大匹配，有重读计算，故结果除以2。

import java.util.*;

	



	public class Main {


	    


	    static int[] nums ;


	    static int n ;


	    static boolean[][] graph;


	    static boolean[] used;


	    static int[] girl;


	    


	    public static void main(String[] args) {


	        


	        Scanner cin = new Scanner(System.in);


	        


	        while (cin.hasNext()) {


	            n = cin.nextInt();


	            nums = new int[n];


	            for (int i = 0; i < n; i ++) {


	                nums[i] = cin.nextInt();


	            }


	            


	            graph = new boolean[n][n];


	            


	            for (int i = 0; i < n; i ++) {


	                for (int j = 0; j < n; j ++) {


	                    if (i == j) {


	                        graph[i][j] = false;


	                    } else {


	                        graph[i][j] = isPrime(nums[i] + nums[j]);


	                    }


	                }


	            }


	            girl = new int[n];


	           


	            int sum = 0;


	           


	            for (int i = 0; i < n; i ++) {


	                 used = new boolean[n];


	                if (find(i)) {


	                    sum += 1;


	                }


	            }


	            


	            System.out.println(sum / 2);


	            


	        }


	    }


	    


	    static boolean find(int x) {


	        for (int i = 0; i < n; i ++) {


	            


	            if (graph[x][i] && used[i] == false) {


	                used[i] = true;


	                if (girl[i] == 0 || find(girl[i])) {


	                    girl[i] = x;


	                    return true;


	                }


	            }


	        }


	        return false;


	    }


	    


	    static boolean isPrime(int n) {


	        if (n == 1) {


	            return false;


	        }


	        for (int i = 2; i <= n/2; i ++) {


	            if (n % i == 0) {


	                return false;


	            }


	        }


	        


	        return true;


	    }


	}