题解 | #素数伴侣#

#include <stdio.h>
#include <string.h>
#include <math.h>
int match(int even[], int odd[], int i, int odd_count, int vis[], int p[]);
int isprime(int n);

int main()
{
  int n;
  while (scanf("%d", &n) != EOF)
  {
    int num;
    int even[n], odd[n];
    int even_count = 0, odd_count = 0;
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &num);
      if (num % 2 == 0)
        even[even_count++] = num;
      else
        odd[odd_count++] = num;
    }
    //0-even_count-1
    int vis[odd_count];
    int p[odd_count];
    for (int i = 0; i < odd_count; i++)
    {
      vis[i] = 0;
      p[i] = -1;
    }
    int cnt = 0;
    for (int i = 0; i < even_count; i++)
    {
      memset(vis, 0, sizeof(vis));
      if (match(even, odd, i, odd_count, vis, p))
        cnt++;
    }
    printf("%d\n", cnt);
  }

  return 0;
}

int match(int even[], int odd[], int i, int odd_count, int vis[], int p[])
{

  for (int j = 0; j < odd_count; j++)
  {
    if (vis[j] == 0 && isprime(even[i] + odd[j]))
    {
      vis[j]=1;
      if (p[j] < 0 || match(even, odd, p[j], odd_count, vis, p))
      {
        p[j] = i;
        return 1;
      }
    }
  }

  return 0;
}

int isprime(int n)
{
  int ret = 1;
  if (n == 1 || (n % 2 == 0 && n != 2))
    ret = 0;
  else
  {
    for (int i = 3; i <= sqrt(n); i += 2)
      if (n % i == 0)
      {
        ret = 0;
        break;
      }
  }
  return ret;
}