77题链接
一个数，能够写成一些质数的和。比如，10可以写成下面五种不同的形式。
1
2
3
4
5
| 7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
|
第一个能被写成大于5000种形式的数是都少呢？
退一步，给定一个数n，如何计算有多少种分解形式呢？这类似于经典的硬币有多少种找法。
硬币倒着排序对解题很有用，参考这种想法，可以先得到一堆质数，然后从小往大的排。
然后呢，找到小于等于n的质数，利用找硬币的算法得到次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| private static int Count(int sum)
{
int index = Array.BinarySearch(primes, sum);
if (index < 0)
{
index = ~index;
}
return Count(sum, index);
}
private static int Count(int sum, int index)
{
if (sum == 0)
{
return 1;
}
if (sum < 0 || index >= primes.Length)
{
return 0;
}
return Count(sum - primes[index], index) + Count(sum, index + 1);
}
|
这里利用了Array.BinarySearch的一个性质，如果没找到，返回的是应该在的位置取反，那么，如果n是质数，那么直接得到了index，如果不是质数，能够得到小于n的质数的位置。
有了Count函数，只需要从小往大遍历，找到第一个超过5000种分解形式的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| private static int[] primes;
private static readonly int Max = 5000;
public static int GetAnswer()
{
primes = Utils.GenPrimes(Max).Reverse().Select(l => (int)l).ToArray();
for (int i = 2; i < Max; i++)
{
int count = Count(i);
if (count >= Max)
{
return i;
}
}
return 0;
}
|