给定数字N(
主数是指素数或可以表示为素数对自身的幂的数，即素数例如素数。 4、27等
我试图使用seive查找所有主数，然后将它们存储在 vector 中(下面的代码)，但是现在我看不到如何找到总和为给定数的最小主数。
这是我的筛子:
#include<algorithm>
#include<vector>
#define MAX 10000
typedef long long int ll;
ll modpow(ll a, ll n, ll temp) {
ll res=1, y=a;
while (n>0) {
if (n&1)
res=(res*y)%temp;
y=(y*y)%temp;
n/=2;
}
return res%temp;
}
int isprimeat[MAX+20];
std::vector<int> primeat;
//Finding all prime numbers till 10000
void seive()
{
ll i,j;
isprimeat[0]=1;
isprimeat[1]=1;
for (i=2; i<=MAX; i++) {
if (isprimeat[i]==0) {
for (j=i*i; j<=MAX; j+=i) {
isprimeat[j]=1;
}
}
}
for (i=2; i<=MAX; i++) {
if (isprimeat[i]==0) {
primeat.push_back(i);
}
}
isprimeat[4]=isprimeat[27]=isprimeat[3125]=0;
primeat.push_back(4);
primeat.push_back(27);
primeat.push_back(3125);
}
int main()
{
seive();
std::sort(primeat.begin(), primeat.end());
return 0;
}
最佳答案
一种方法可能是将所有小于或等于N的主语存储在排序的列表中-将该列表称为L-并递归搜索最短序列。最简单的方法是“贪婪”:尽早选择最大的跨度/数字。
对于N = 14，您将拥有L = {2,3,4,5,7,8,9,11,13}，因此您想创建一个尝试这些序列的算法/过程:
13太小13 + 13-> 13 + 2将太大11太小11 + 11-> 11 + 4将太大11 + 3是一个匹配项。 您可以通过在每次求和函数中需要另一个基本函数的情况下使搜索函数递归来继续该过程，以使出现次数最少。为此，您可以在每个位置中选择最大的->最小的本原语(总和中的第一，第二等)，并且仅当到目前为止总和中的主语足够小以至于一个额外的主数时，才在总和中包含另一个数字。不会超过
N。我必须做一个工作的例子，以找到一个足够小的
N，它的总和不会只有2个数字。请注意，因为您可以将任何自然数表示为自然数的最多4个平方的和，并且L的集合比平方的集合更密集，所以我认为很少有3的结果或更多您想要手动计算的N。动态编程方法
我必须澄清一下，“贪心”与“动态编程”不同，它可能会导致次优结果。确实有一个DP解决方案。同样，我不会用代码编写最终过程，而是将其解释为从中得出可行的DP解决方案的引用点。
为此，我们需要从头开始构建解决方案。您需要的是一种结构，该结构可以存储已知的所有数字的解决方案，直到某些
N为止，此列表可以以最佳方式递增地添加到较大的N中。考虑到对于任何
N，如果是原始的，那么N的术语数仅为1。这适用于N=2-5,7-9,11,13,16,17,19。所有其他N的术语数必须至少为两个，这意味着它是两个primatic的总和，或者是primatic和其他N的总和。前几个例子并不简单:
6 -可以是
2+4或3+3，这里的所有术语本身都是原始的，因此6的最小术语数是2。10 -可以是
2+8，3+7，4+6或5+5。但是6不是主要的，取出该解决方案至少要保留2个条件。12 -可以是
2+10，3+9，4+8，5+7或6+6。在这些6+6和2+10中包含非主语，而其他不包含，因此同样最少2个字。14 -ditto，存在两种基本解决方案:
3+11，5+9和7+7。存储所有这些解决方案的结构需要能够在等级/项数相等的解决方案之间进行迭代。您已经有了一个基本原理列表，这也是只需要一个术语的解决方案的列表。
Sol[term_length] = list(numbers)。您还将需要一个函数/缓存来查找某些N的最短长度，例如S(N) = term_length iif N in Sol[term_length]Sol[1] = {2,3,4,5 ...}和更高版本的Sol[2] = {6,10,12,14 ...}和Sol[3]等。可以使用
Sol[1]中的一个词作为主语找到任何解决方案。在Sol[2]中可以找到任何需要两个定理的解决方案。任何需要3的解决方案都将在Sol[3]等中。您需要在此处识别的是，对于某些
S(N) = 3惯用语，数字Sol[1][a] + Sol[1][b] + Sol[1][c]可以表示为a,b,c，但也可以表示为Sol[1][a] + Sol[2][d]，因为所有Sol[2]必须可表示为Sol[1][x] + Sol[1][y]。该算法实际上会搜索给定的
Sol[1]的N，然后使用增加的Sol[1] + Sol[K]来查找K，但是要做到这一点，您将需要大致按照此处显示的形式的S和Sol结构(或可以类似的方式进行访问/查询) 。工作实例
使用以上内容作为指导，我将其快速组合在一起，甚至显示了它使用了哪个长期总和。
https://ideone.com/7mYXde
如果需要，我可以深入解释代码，但是真正的DP部分在40-64行附近。递归深度(也就是总和中附加项的数量)是
k，这是一个简单的双重迭代器while循环，使用第k个已知的解决方案和底数检查总和是否可行，如果可以，则完成，否则请检查k + 1个解决方案(如果有)。 Sol和S如所述工作。唯一令人困惑的部分可能是使用反向迭代器，只是为了使
!= end()检查在while条件下保持一致(end不是有效的迭代器位置，而begin是，因此!= begin的写法将有所不同)。编辑-仅供引用，至少需要3个字词的第一个数字是
959-必须将我的算法运行到1000个数字才能找到它。它是6 + 953(原始)的总和，无论您如何拆分6，它仍然是3个术语。关于c++ - 如何找到与给定数字相加的最小本数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38203226/