题解 | #素数伴侣#

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

namespace HJ28
{
    internal class Program
    {
        /// <summary>素数伴侣类，记录了能够配成素数化伴侣的奇数偶数 </summary>
        class PrimeCompanion
        {
            public int OddNumber;
            public int EvenNumber;

            public PrimeCompanion()
            {

            }

            public PrimeCompanion(int oddNumber, int evenNumber)
            {
                OddNumber = oddNumber;
                EvenNumber = evenNumber;
            }
        }

        static void Main(string[] args)
        {
            string inuptStr = Console.ReadLine();
            int count = int.Parse(inuptStr);
            inuptStr = Console.ReadLine();
            string[] strings = inuptStr.Split();

            //分奇偶两组数去匹配，因为奇数+奇数=偶数 偶数+偶数=偶数 偶数就不是素数
            //奇数数字列表
            List<int> oddNumbers = new List<int>();
            //偶数数字列表
            List<int> evenNumbers = new List<int>();
            for (int i = 0; i < strings.Length; i++)
            {
                int number = int.Parse(strings[i]);
                if (number % 2 == 0)
                {
                    evenNumbers.Add(number);
                }
                else
                {
                    oddNumbers.Add(number);
                }
            }

            //用于记录偶数匹配了哪个奇数，如果奇数部分值不为零，则是匹配上了
            List<PrimeCompanion> companions = new List<PrimeCompanion>();
            for (int i = 0;i < evenNumbers.Count; i++)
            {
                companions.Add(new PrimeCompanion(0, evenNumbers[i]));
            }

            for (int i = 0; i < oddNumbers.Count; i++)
            {
                //每一个奇数都需要重置匹配标记，因为是新的匹配，不能让以前的匹配记录影响结果
                bool[] isVisited = new bool[evenNumbers.Count];
                FindMatch(oddNumbers[i], evenNumbers, isVisited, companions);
            }

            //前面我们已经将素数对的偶数部分全部赋值，因此此时只需要判断奇数部分不为0则说明配对成功
            Console.WriteLine(companions.Where(x => x.OddNumber != 0).Count());

        }

        static bool FindMatch(int x, List<int> evenNumbers, bool[] isVisited, List<PrimeCompanion> matches)
        {
            for (int i = 0; i < evenNumbers.Count; i++)
            {
                //假如没有进行匹配过，并且能匹配上，先打上标记，并没有定下这一配对
                if (isVisited[i] == false && IsPrime(x + evenNumbers[i]))
                {
                    isVisited[i] = true;

                    //这里开始决定是否定下配对
                    //假如i位置的偶数没有匹配，直接让该位置的偶数与x匹配：先到先得
                    //或者i位置的偶数已经匹配上了一奇数，并且这个奇数能重新找到匹配，则让出：能让则让，从而达到最大匹配
                    if (matches[i].OddNumber == 0 || FindMatch(matches[i].OddNumber, evenNumbers, isVisited, matches))
                    {
                        matches[i].OddNumber = x;
                        return true;
                    }
                }
            }
            return false;
        }

        /// <summary> 判断一个数是否为素数 </summary>
        static bool IsPrime(int number)
        {
            if (number <= 1)
            {
                return false;
            }

            //这里有一个公理，一个数最多只有一个大于它的平方根的约数，
            //另一个约数一定小于它的平方根，
            //因此我们只需要遍历它的平方根次就能知道它是否是素数，减少遍历时间
            for (int i = 2; i < Math.Sqrt(number) + 1; i++)
            {
                if (number % i == 0)
                {
                    return false;
                }
            }
            return true;
        }

    }
}