题解 | #素数伴侣#

#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;
}