欧拉项目 | 题目51 | 找出最小的能够通过改变同一部分得到八个质数的质数

通过置换*3的第一位得到的9个数中，有六个是质数：13,23,43,53，73和83。

通过用同样的数字置换56**3的第三位和第四位，这个五位数是第一个能够得到七个质数的数字，得到的质数是：56003, 56113, 56333, 56443, 56663, 56773, 和 56993。因此其中最小的56003就是具有这个性质的最小的质数。

找出最小的质数，通过用同样的数字置换其中的一部分（不一定是相邻的部分），能够得到八个质数。

我折腾这道题很久很久，也没能得到解，于是乎，我Google了Prime digit replacements（这是英文标题），看了看别人的分析，找到了问题的关键点：如何选出可能是解的质数。下面也着重讲解这个。

首先说明一下，我直觉觉得这道题的解答是六位数，仅仅是直觉，因为做了很多欧拉项目的题目。其实，如果答案不是六位数，比如是五位数，分析方法是不变的。

变化几个数字呢？变化的第几位数呢？
肯定不能变化最后一位数。因为，质数的最后一位只可能是1，3，7，9，离八个质数还很远呢。

变化几个数字呢？
假设是1个，考虑下被三整除的性质。
假设除去变化的数字之外的五位数之和模三等于一：那么变化的这一位数不能是2，5，8。最多只能得到七个质数。
假设除去变化的数字之外的五位数之和模三等于二：那么变化的这一位数不能是1，4，7。同上。
所以不可能只变化一个数字。

假设是2个呢？按照上面的思路，可以得出结论，不可能只变化两个数字。

假设是3个呢？同一数字*3，模三等于0，不影响其余三位数字之和模三的结果，不会推出矛盾。
4个，5个？！也是不可能的。

至此，我们得到一个结论：六位数字，最后一位不能是变化的，同时，每次要变化三个数字。
那么，题目的结果一定要满足下面的模式：

1	string[] patterns = new string[] { "110001", "101001", "100101", "100011", "011001", "010101", "010011", "001011", "000111" };

其中，0表示变化的数字，也就是说，对于某个质数，这三位要一样；1表示不变化的数字。

现在，我们来生成可能的候选质数：

我们先生成所有的六位数质数：

long[] primes = Utils.GenPrimes(100000, 1000000);

//[begin, end)
public static long[] GenPrimes(long begin, long end)
{
    List<long> primes = new List<long>();
    for (long i = begin; i < end; i++)
    {
        if (Utils.IsPrime(i))
        {
            primes.Add(i);
        }
    }

    return primes.ToArray();
}

结果有将近七万的质数。

把符合模式的数字筛选出来，我用了很笨的方法，但是数据量不大，无所谓了，速度还是很快：

primes = primes.Where(l =>
{
    for (int i = 0; i < patterns.Length; i++)
    {
        string pattern = patterns[i];
        List<char> chars = new List<char>();
        for (int j = 0; j < pattern.Length; j++)
        {
            if (pattern[j] == '0')
            {
                chars.Add(l.ToString()[j]);
            }
        }

        if (chars.Distinct().Count() == 1)
        {
            return true;
        }
    }

    return false;
}).ToArray();

过滤完之后，只有不到4000个符合题目的质数了。

接下来，我使用了一套很笨的连通图的算法找到这八个质数，复杂度很高，但是基于4000个数，还是很快就能得出结果了。

当然，如果你也Google下Prime digit replacements的话，你会找到几个非常赞的解法。