找到求和小于1000的给定整数所需的最少质数
找到求和小于1000的给定整数所需的最少质数
提问于 2019-06-19 02:05:17
这是我最近面临的一个编程挑战。
给你一个小于1000的数，你需要确定需要多少个最小数目的素数，这个数之和是给定的数。，
，You，you，of，你需要确定需要多少个最小数目的素数。
示例：
12: 2(自12=7+5开始) 14: 2(自14 = 7+7)
如果不可能将给定的数拆分为质数和，则返回-1。
以下是一些测试用例：
88:2 117:3 374:2 363:3 11:1
回答 1
Stack Overflow用户
发布于 2019-06-19 02:27:18
这只是经典knapsack problem的一个变体。
在最初的背包问题和这个问题中，我们都有一组可以选择的项目。每一项都有它的成本/价值，我们正在优化它，并且它有一个我们受其限制的大小。在最初的背包问题中，我们希望最大化利润，同时将权重保持在设定的最大值之下。在这里，我们想要最小化素数的数量，而和恰好是我们给定的数量。
我们可以更改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表中的所有值或使用类似于原始背包问题的记忆法来计算DP[numPrimes][N]。
正如Willem Van Onsem指出的那样，这个问题是一个特例，因为每个小于4* 10^18的偶数都可以表示为两个素数的和，这允许一个更快的解决方案，其复杂性与用于测试素数的算法相同。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56654738
复制相关文章
相似问题