118 Pandigital Prime Sets
原题链接：https://projecteuler.net/problem=118
使用数字 1 到 9 可以随意的组成一些整数，形成一个个集合。集合比较特殊，每一个数字都是质数。
问，每个数字使用一次，能够组成多少个都是质数元素的集合呢？
除了 2 以外，质数不能以基数结尾，那么长度为 9 的数字也就 个，其他长度应该少很多，我们假设一共有 300k 个吧，下一步需要确认这些数字中哪些是质数。9 个数字最大是，平方小于五万，而五万以内有大约 5k 个质数，那么最多需要 1.5G 次运算得到所有能组成集合的候选质数。这个数量级完全是可以接受的。
不过组成数字的时候，需要判断一下这个数是否有重复数字，那么大约 个数字需要处理，最多 10 次就足够了，那么这需要约 10G 次运算。其实在拼接的过程中，如果 位数字有重复的话，那么就不需要再拼接 位了，那么可以去掉非常多的可能性，那么应该很快得到候选质数。另外，一般情况下从 到 位，我们都是直接把之前的数乘以 10，然后加一个值，相当于往后面加数字，这里我采用了向前面加数字，因为除了 2 之外，其他质数的尾数都是奇数，这样可以少处理一些数。
得到结果之后我发现长度为 9 的数组是空的，这非常合理。数字不重复，长度 9，就是每个数字用一遍，那么这个数的各个数字和肯定能被 3 整除，那么数本身不是质数。有了这一点，能把长度少一位，那么生成候选质数能够快不少。
所有的候选质数按照长度放到不同的数组中，这样，后续容易根据长度来选择元素构成最终的集合。
// Main
// length 1 to 9
for (int i = 0; i < 10; i++)
{
unique.Add(new List<int>());
}
var primes = Utils.GenPrimes(10000).Where(p => p != 0).ToArray();
for (int i = 1; i < 10; i += 2)
{
GenPrimes(i, 1, primes);
}
unique[1].Add(2);
private void GenPrimes(int value, int length, long[] primes)
{
if (!Utils.IsPandigital(value))
return;
if (Utils.IsPrime(value, primes))
unique[length].Add(value);
if (length >= 8)
return;
for (int i = 1; i < 10; i++)
{
GenPrimes(value + i * pow[length], length + 1, primes);
}
}
public static bool IsPandigital(int y)
{
int[] digits = new int[10];
while (y != 0)
{
digits[y % 10]++;
y /= 10;
}
return digits.All(i => i == 0 || i == 1);
}
// Main
foreach (var p in unique)
{
p.Sort();
p.Reverse();
}
int count = 0;
for (int i = 8; i >= 2; i--)
{
var list = unique[i];
foreach (var start in list)
{
GenSets(new List<int>() { start }, i, i, ref count);
}
}
return count.ToString();
private void GenSets(List<int> elements, int length, int lastLength, ref int count)
{
if (length == 9)
{
if (Utils.IsPandigital(elements))
{
count++;
}
return;
}
if (!Utils.IsPandigital(elements))
{
return;
}
var remain = 9 - length;
var begin = Math.Min(remain, lastLength);
for (int i = begin; i >= 1; i--)
{
var list = unique[i];
int start = 0;
if (lastLength == i)
{
start = list.IndexOf(elements.Last()) + 1;
}
for (int j = start; j < list.Count; j++)
{
var n = list[j];
var newlist = new List<int>(elements.Count + 1);
newlist.AddRange(elements);
newlist.Add(n);
GenSets(newlist, length + i, i, ref count);
}
}
}