题解 | #素数伴侣#

using System;
using System.Collections.Generic;
using System.Linq;

namespace ProjectSample
{
    //HJ28
    class Program
    {
        static void Main(string[] args)
        {
            /// input setup
            int total = int.Parse(Console.ReadLine());
            int[] num_arr = Console.ReadLine().Split(" ")
                .Select(s => int.Parse(s)).ToArray();

            List<int> Odds = new List<int>();
            List<int> Evens = new List<int>();

            foreach (var num in num_arr) 
            {
                if (num % 2 == 0)
                    Odds.Add(num);
                else
                    Evens.Add(num);
            }

            /// algorithm
            // contain matched even
            int[] matcheven = new int[Evens.Count];
            // record how many partener exists
            int count = 0;
            // go through odds
            for (int j = 0; j < Odds.Count; j++) 
            {
                // if relavent even has been visited
                bool[] v = new bool[Evens.Count];
                // if matching, count++
                if (CouldFind(Odds[j], matcheven, Evens, v)) 
                {
                    count++;
                }
            }
            Console.WriteLine(count);
        }

        // whether x could find a matching even
        static bool CouldFind(int x, int[] matcheven, List<int> evens, bool[] v) 
        {
            for (int i = 0; i < evens.Count; i++) 
            {
                // this even isn't visited, and could match x
                if (IsPrime(x + evens[i]) && v[i] == false) 
                {
                    v[i] = true;
                    /* if even[i] is not matched, match it with x; if even[i] matched, and its odds-partener could match another one,
                     let its partener match another one, match it with x*/
                    if (matcheven[i] == 0 || CouldFind(matcheven[i], matcheven, evens, v))
                    {
                        matcheven[i] = x;
                        return true;
                    }
                }
            }
            return false;
        }

        static bool IsPrime(int num) 
        {
            if (num % 2 == 0)
                return false;
            if (num == 1)
                return true;
            for (int i = 3; i <= Math.Sqrt(num); i += 2) 
            {
                if (num % i == 0)
                    return false;
            }
            return true;
        }
    }
}