kar*_*ddy 0 algorithm dynamic-programming greedy
这是我最近面临的编程挑战。
您得到的数字小于1000，您需要确定求和到给定数字的素数最少为多少。
例子：
Run Code Online (Sandbox Code Playgroud)12: 2 (since 12=7+5) 14: 2 (since 14 = 7+7)如果不可能将给定的数字分解为素数之和，则返回-1。
以下是一些测试用例：
Run Code Online (Sandbox Code Playgroud)88:2 117:3 374:2 363:3 11:1
简而言之：一个数字的最大质数为3。由于只有168个质数小于1，000，因此我们可以穷尽地使用两个质数的组合，或者默认使用3。通过使用一些额外的属性，我们可以轻松找出最小数量的元素，甚至构造一个集合这些数字中。
如果我们假设我们可以访问最多1000个素数列表，则可以解决问题，其中有168个。
假设数字是质数，那么答案显然是1。
对于非素数，我们将必须找到不同的方法来解决问题。
每个大于2的偶数整数都可以表示为两个素数之和。
这个猜想通常没有得到证明，但是至少知道对于所有4×10 18的数字都成立。
因此，这意味着for n = 2的答案为1，而对于偶数 n > 2的答案为2（因为只有一个偶数素数）。
在数字为奇数且非素数的情况下，我们知道素数的最大数为3。确实，因为如果我们3从该数字中减去，我们将得到一个偶数，它可以由2三个或三个元素组成。显然，这被称为哥德巴赫边际猜想[wiki]：
每个大于5的整数都可以写成三个素数的总和。
改善上限的唯一方法是找到两个合起来等于给定数字的素数。因此，这需要迭代所有质数（最多1'000），并检查n-p是否也是质数。但是，正如@AlexanderZhang所说的，我们可以减去2，因为这是唯一的导致偶数的偶数，因此是质数的候选者。
综上所述，基本上有以下几种情况：
2，我们知道这是最小的，因为除了2，没有偶数。2是质数，并且n-2是质数，我们知道没有更好的解决方案，因为n不是质数。最后2减数之外，没有其他质数是偶数，因此我们可以再次使用哥德巴赫猜想。因此，我们可以实现如下算法：
primes1000 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}
def min_prime(n):
if n < 2:
return -1
if n in primes1000:
return 1
# 2 and 3 are prime numbers prime number
# so all values here are > 3
if n % 2 == 0:
return 2 # Goldbach's conjecture, so 2
if n-2 in primes1000:
return 2
return 3 # fallback on 3
例如：
>>> min_prime(12)
2
>>> min_prime(14)
2
>>> min_prime(88)
2
>>> min_prime(117)
3
>>> min_prime(374)
2
>>> min_prime(363)
3
>>> min_prime(11)
1
我们可以使用相同的方法生成素数，例如：
def find_sum2(n):
for p in primes1000:
if n-p in primes1000:
return (p, n-p)
def min_prime_tuple(n):
if n < 2:
return None
if n in primes1000:
return (n,)
if n % 2 == 0:
return find_sum2(n)
if n-2 in primes1000:
return (2, n-2)
return (3, *find_sum2(n-3))
例如：
>>> min_prime_tuple(12)
(5, 7)
>>> min_prime_tuple(14)
(3, 11)
>>> min_prime_tuple(88)
(5, 83)
>>> min_prime_tuple(117)
(3, 5, 109)
>>> min_prime_tuple(374)
(7, 367)
>>> min_prime_tuple(363)
(3, 7, 353)
>>> min_prime_tuple(11)
(11,)
我们可以通过从迭代器大于的那一刻起就切断线性搜索来提高效率n，但这通常不会产生太大的区别，因为小于1000的质数数量非常少。
由于n上限为1'000，所以没有大哦。此外，如果n无界，我们不知道这个猜想是否仍然成立。
如果我们假设猜想成立，则在O（g×c）中生成元组，用g生成所有素数直到n的时间，用c检验数字是否为素数的时间。
如果我们在Python中对上述不是很有效实现的方法进行基准测试，我们将实现以下基准测试：
>>> timeit(lambda: list(map(min_prime_tuple, range(0,1000))), number=10_000)
4.081021320000218
因此，这意味着，如果我们以10,000次为不超过1,000的所有数字构造元组，则将在Intel®Core™i7-7500U CPU @ 2.70GHz上于4.08秒内完成。因此，这意味着我们可以在408.1μs内检查整个范围，或者在0.408μs内检查一个随机数。
这只是经典背包问题的一个变体。
在最初的背包问题和本背包问题中，我们都有一组项目可供选择。每个项目都有我们正在优化的成本/价值，并且它的大小受到我们的限制。在最初的背包问题中，我们希望最大化利润，同时将权重保持在设定的最大值以下。在这里，我们希望最小化素数的数量，而总和正是我们给定的数量。
我们可以改变我们的DP阵列，从而定义DP[i][j]是需要和准确的素数的最小数量j仅使用第一i质数或无穷大，如果它是不可能总结到j只使用第一个i素数，而我们的复发关系变得DP[i][j] = min(DP[i - 1][j], DP[i][j - p[i]] + 1)哪里p[i]是i第素数。DP[numPrimes][N]然后，可以通过计算DP表中的所有值或使用类似于原始背包问题的备忘录来计算。
正如Willem Van Onsem指出的那样，此问题是一种特殊情况，因为每个小于4 * 10 ^ 18的偶数都可以表示为两个质数之和，从而可以更快地解决问题，其复杂度与您使用的算法相同用于测试素数。