There are several test cases.
Each test start with positive integers N(1 ≤ N ≤ 100),which means there are N extraterrestrials on the alien planet.?
The following N lines,each line contains a positive integer pi ( 2 ≤ pi ≤10^18),indicate the i-th extraterrestrial is born with pi number.
The input will finish with the end of file.
For each the case,your program will output maximum number of friend pair.
Sample Input
3
2
2
3
4
2
5
3
8
Sample Output
1
2
思路：
这题用普通的素数判断是会超时的，所以要用大数的素数判断（拉宾米勒测试 ），之后就是一个二分匹配的模板就行了。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<time.h>
using namespace std;
#define T 1100
#define inf 0x3f3f3f3f
#define mod 1000000007
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef unsigned long long ll;
int V;
int g[T][T];
int cx[T],cy[T];
int mk[T];
//*******************
//拉宾米勒测试
ll MIN;
ll mult_mod(ll a,ll b,ll n)
{
ll s=0;
while(b)
{
if(b&1) s=(s+a)%n;
a=(a+a)%n;
b>>=1;
}
return s;
}
ll pow_mod(ll a,ll n)
{
ll s=1;
while(b)
{
if(b&1) s=mult_mod(s,a,n);
a=mult_mod(a,n);
b>>=1;
}
return s;
}
bool Prime(ll n)
{
ll u=n-1,pre,x;
int i,j,k=0;
if(n==2||n==3||n==5||n==7||n==11) return 1;
if(n==1||(!(n%2))||(!(n%3))||(!(n%5))||(!(n%7))||(!(n%11))) return 0;
for(;!(u&1);k++,u>>=1);
srand((ll)time(0));
for(i=0;i<5;i++)
{
x=rand()%(n-2)+2;
x=pow_mod(x,u,n);
pre=x;
for(j=0;j<k;j++)
{
x=mult_mod(x,x,n);
if(x==1&&pre!=1&&pre!=(n-1))
return 0;
pre=x;
}
if(x!=1) return false;
}
return true;
}
//************************
void add_edge(int u,int v)
{
g[u][v]=1;
g[v][u]=1;
}
int dfs(int v)
{
for(int i=0;i<V;++i){
if(g[v][i]&&!mk[i]){
mk[i]=1;
if(cy[i]==-1||dfs(cy[i])){
cx[v]=i;
cy[i]=v;
return 1;
}
}
}
return 0;
}
int bipartite_matching()
{
int res=0;
memset(cx,-1,sizeof(cx));
memset(cy,sizeof(cy));
for(int i=0;i<V;++i){
if(cx[i]==-1){
memset(mk,sizeof(mk));
res+=dfs(i);
}
}
return res;
}
int main()
{
#ifdef zsc
freopen("input.txt","r",stdin);
#endif
int i,j;
ll a[T];
while(~scanf("%d",&V))
{
memset(g,sizeof(g));
for(i=0;i<V;++i)
scanf("%lld",&a[i]);
for(i=0;i<V;++i){
for(j=i+1;j<V;++j){
ll tmp = a[i]+a[j];
if(Prime(tmp)){
add_edge(i,j);
}
}
}
printf("%dn",bipartite_matching()/2);
}
return 0;
}
