题解 | #素数伴侣#
素数伴侣
https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e
#include<stdio.h>
#include<string.h>
int n;
int j1=0;
int j2=0;
int a[105]={0};
int odd[105]={0};
int even[105]={0};
int cnt=0;
int used[105]={0};
int linked[105]={0};
int isprime(int x,int y)
{
int z=x+y;
if(z==1){return 0;}
if(z==2){return 1;}
for(int i=2;i<z;i++)
{
if(z%i==0){return 0;}
}
return 1;
}
int find(int i)
{
for(int j=1;j<=j2;j++)
{
if(isprime(even[i-1],odd[j-1])==1&&used[j]==0)
{
used[j]=1;
if(linked[j]==0){linked[j]=i;return 1;}
else if(linked[j]!=0)
{
if(find(linked[j]))
{
linked[j]=i;
return 1;
}
}
}
}
return 0;
}
int main(void)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d ",&a[i]);
if(a[i]%2==0){even[j1++]=a[i];}
else{odd[j2++]=a[i];}
}
if(j1==0||j2==0){cnt=0;}
else{
for(int i=1;i<=j1;i++)
{
memset(used,0,sizeof(used));
if(find(i)){cnt++;}
}
}
printf("%d",cnt);
//printf("%d",isprime(3,6));
return 0;
}
