找到求和为小于 1000 的给定整数所需的最少素数
Find least number of primes required to sum up to a given integer less than 1000
这是我最近面临的编程挑战。
You are given a number less than 1000 you need to determine how many least number of primes are required that sum to given number.
Examples:
12: 2 (since 12=7+5)
14: 2 (since 14 = 7+7)
If it is not possible to split given number into sum of primes then return -1.
Here are few test cases:
88:2
117:3
374:2
363:3
11:1
这只是经典 knapsack problem 的变体。
在原来的背包问题和这个背包问题中，我们都有一组可以从中选择的物品。每个项目都有我们正在优化的 cost/value，并且它的大小受到我们的限制。在最初的背包问题中，我们希望在将重量保持在设定的最大值以下的同时最大化利润。在这里，我们想要最小化质数的数量，而总和恰好是我们给定的数。
我们可以更改我们的 DP 数组的定义，使得 DP[i][j] 是仅使用第一个 i 个素数或无穷大的总和恰好 j 所需的最小素数数量，如果仅使用第一个 i 个素数不可能求和为 j，我们的递推关系变为 DP[i][j] = min(DP[i - 1][j], DP[i][j - p[i]] + 1)，其中 p[i] 是第 i 个素数。 DP[numPrimes][N] 然后可以通过计算 DP table 中的所有值或使用类似于原始背包问题的记忆来计算。
正如 Willem Van Onsem 所指出的，这个问题是一个特例，因为每个小于 4 * 10^18 的偶数都可以表示为两个素数之和，这样可以更快地解决复杂度相同的问题作为您用来测试素数的算法。
简而言之：一个数的最大质数个数是3。由于小于1'000的素数只有168个，我们可以穷举两个素数的组合，或者默认3个。通过使用一些额外的性质，我们可以很容易地找出元素的最小数量，甚至构造一个集合这些数字。
如果我们假设我们可以访问最多 1'000 个素数列表，我们就可以解决这个问题，其中有 168 个。
鉴于这个数是质数，那么显然答案是1.
对于non-prime个数字，我们将不得不寻找不同的方法来解决问题。
Goldbach's conjecture [wiki] 表示
Every even integer greater than 2 can be expressed as the sum of two primes.
这个猜想未得到一般性证明，但至少知道对所有高达4×1018的数字都成立。
这意味着对于 n = 2，答案是 1，对于 even n > 2，答案是 2（因为只有一个偶素数）。
如果是奇数，non-prime，我们知道素数的最大个数是3。实际上，因为如果我们从该数字中减去 3，我们会得到一个偶数，它可以由 2 或三个元素组成。显然这被称为 Goldbach's marginal conjecture [wiki]:
Every integer greater than 5 can be written as the sum of three primes.
我们可以改进上限的唯一方法是找到 两个 总和等于给定数字的质数。因此，这需要遍历所有素数（最多 1'000），并检查 n - p 是否也是素数。然而，正如 所说，我们可以减去 2，因为这是唯一会导致奇数的偶数，因此是质数的候选者。
所以总结起来，基本上有以下几种情况：
- 对于n < 2，没有质数，显然失败了；
- 对于n一个质数，答案当然是一，因为我们可以简单地使用那个数；
- 对于大于二的偶数，我们可以使用哥德巴赫猜想，因此return
2，我们知道这是最小的，因为除了对于2，没有偶数素数；
- 对于大于二的奇数，我们知道如果n-2是质数，那么这个数就是2，因为
2是质数，并且n-2是质数，我们知道没有更好的解，因为n不是质数；最后
- 对于n-2不是质数的奇数，我们知道n-3是偶数 根据哥德巴赫猜想，我们可以构造三个素数的和。我们知道这是最优的，因为除
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，因此没有 big-oh。此外，如果 n 是无界的，我们不知道猜想是否仍然成立。
如果我们假设猜想成立，那么生成元组的时间为O(g×c)，时间为g生成最多 n 的所有素数，以及 c 检查数字是否为素数的时间。
如果我们在 Python 中对上述实施效率不高的方法进行基准测试，我们将实现以下基准：
>>> timeit(lambda: list(map(min_prime_tuple, range(0,1000))), number=10_000)
4.081021320000218
这意味着如果我们为 1'000 以内的所有数字构造元组 10'000 次，这在 Intel(R) Core(TM) i7- 7500U CPU @ 2.70GHz。因此，这意味着我们可以在 408.1 μs 内检查整个范围，或者大约在 0.408 μs 内检查随机数。
这是我最近面临的编程挑战。
You are given a number less than 1000 you need to determine how many least number of primes are required that sum to given number.
Examples:
12: 2 (since 12=7+5) 14: 2 (since 14 = 7+7)If it is not possible to split given number into sum of primes then return -1.
Here are few test cases:
88:2 117:3 374:2 363:3 11:1
这只是经典 knapsack problem 的变体。
在原来的背包问题和这个背包问题中，我们都有一组可以从中选择的物品。每个项目都有我们正在优化的 cost/value，并且它的大小受到我们的限制。在最初的背包问题中，我们希望在将重量保持在设定的最大值以下的同时最大化利润。在这里，我们想要最小化质数的数量，而总和恰好是我们给定的数。
我们可以更改我们的 DP 数组的定义，使得 DP[i][j] 是仅使用第一个 i 个素数或无穷大的总和恰好 j 所需的最小素数数量，如果仅使用第一个 i 个素数不可能求和为 j，我们的递推关系变为 DP[i][j] = min(DP[i - 1][j], DP[i][j - p[i]] + 1)，其中 p[i] 是第 i 个素数。 DP[numPrimes][N] 然后可以通过计算 DP table 中的所有值或使用类似于原始背包问题的记忆来计算。
正如 Willem Van Onsem 所指出的，这个问题是一个特例，因为每个小于 4 * 10^18 的偶数都可以表示为两个素数之和，这样可以更快地解决复杂度相同的问题作为您用来测试素数的算法。
简而言之：一个数的最大质数个数是3。由于小于1'000的素数只有168个，我们可以穷举两个素数的组合，或者默认3个。通过使用一些额外的性质，我们可以很容易地找出元素的最小数量，甚至构造一个集合这些数字。
如果我们假设我们可以访问最多 1'000 个素数列表，我们就可以解决这个问题，其中有 168 个。
鉴于这个数是质数，那么显然答案是1.
对于non-prime个数字，我们将不得不寻找不同的方法来解决问题。
Goldbach's conjecture [wiki] 表示
Every even integer greater than 2 can be expressed as the sum of two primes.
这个猜想未得到一般性证明，但至少知道对所有高达4×1018的数字都成立。
这意味着对于 n = 2，答案是 1，对于 even n > 2，答案是 2（因为只有一个偶素数）。
如果是奇数，non-prime，我们知道素数的最大个数是3。实际上，因为如果我们从该数字中减去 3，我们会得到一个偶数，它可以由 2 或三个元素组成。显然这被称为 Goldbach's marginal conjecture [wiki]:
Every integer greater than 5 can be written as the sum of three primes.
我们可以改进上限的唯一方法是找到 两个 总和等于给定数字的质数。因此，这需要遍历所有素数（最多 1'000），并检查 n - p 是否也是素数。然而，正如 2，因为这是唯一会导致奇数的偶数，因此是质数的候选者。
所以总结起来，基本上有以下几种情况：
- 对于n < 2，没有质数，显然失败了；
- 对于n一个质数，答案当然是一，因为我们可以简单地使用那个数；
- 对于大于二的偶数，我们可以使用哥德巴赫猜想，因此return
2，我们知道这是最小的，因为除了对于2，没有偶数素数； - 对于大于二的奇数，我们知道如果n-2是质数，那么这个数就是2，因为
2是质数，并且n-2是质数，我们知道没有更好的解，因为n不是质数；最后 - 对于n-2不是质数的奇数，我们知道n-3是偶数 根据哥德巴赫猜想，我们可以构造三个素数的和。我们知道这是最优的，因为除
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，因此没有 big-oh。此外，如果 n 是无界的，我们不知道猜想是否仍然成立。
如果我们假设猜想成立，那么生成元组的时间为O(g×c)，时间为g生成最多 n 的所有素数，以及 c 检查数字是否为素数的时间。
如果我们在 Python 中对上述实施效率不高的方法进行基准测试，我们将实现以下基准：
>>> timeit(lambda: list(map(min_prime_tuple, range(0,1000))), number=10_000)
4.081021320000218
这意味着如果我们为 1'000 以内的所有数字构造元组 10'000 次，这在 Intel(R) Core(TM) i7- 7500U CPU @ 2.70GHz。因此，这意味着我们可以在 408.1 μs 内检查整个范围，或者大约在 0.408 μs 内检查随机数。