如何找到总和为给定数字的最少数量的灵长类动物

Question

给定一个数 N (<=10000)，找出总和为 N 的最小素数个数。

素数是指既可以是素数也可以表示为素数对其自身的幂的数，即素数^素数，例如4、27 等

我试图使用 seive 找到所有原始数，然后将它们存储在一个向量中（下面的代码），但现在我看不到如何找到总和为给定数字的最小原始数。

这是我的筛子：

#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;
}

Answer 1

一种方法可能是将所有小于或等于 N 的元学存储在排序列表中 - 调用此列表 L - 并递归搜索最短序列。最简单的方法是 "greedy"：尽早选择最大的跨度/数字。

对于 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 比正方形集合更密集，所以我认为您很少有对于您想要手动计算的任何 N，结果为 3 或更多。

动态编程方法

我必须澄清 'greedy' 与 'dynamic programming' 不同，它可以给出次优的结果。不过，这确实有一个 DP 解决方案。同样，我不会用代码编写最终过程，而是将其解释为一个参考点，以便从中制定有效的 DP 解决方案。

为此，我们需要自下而上地构建解决方案。你需要的是一个结构，它可以存储所有数字的已知解决方案，最多 N，这个列表可以以最佳方式增量添加到更大的 N。

考虑对于任何 N，如果它是原始的，那么 N 的项数仅为 1。这适用于 N=2-5,7-9,11,13,16,17,19。所有其他 N 的项数必须至少为两个，这意味着它要么是两个 primatics 的总和，要么是一个 primatic 和 some other N[=142= 的总和].

前几个重要的例子：

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 - 同上，存在二元解：3+11、5+9、7+7.

用于存储所有这些解决方案的结构需要能够遍历相同等级/项数的解决方案。您已经有了一个 primatics 列表，这也是只需要一个术语的解决方案列表。

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] 中的一个原始术语找到。任何需要两个 primatics 的解决方案都可以在 Sol[2] 中找到。任何需要 3 的解决方案都将在 Sol[3] 等
中
这里你需要认识到的是，一个数字S(N) = 3对于一些a,b,c primatics可以表示为Sol[1][a] + Sol[1][b] + Sol[1][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 个已知解决方案和 primatics 求和，如果是，那么我们就完成了如果没有，则检查 k+1 个解决方案（如果有）。 Sol 和 S 按照说明工作。

唯一令人困惑的部分可能是反向迭代器的使用，它只是为了使 != end() 检查 while 条件的一致性（end 不是有效的迭代器位置，但 begin 是，所以 != begin会有不同的写法）。

编辑 - 仅供参考，第一个至少需要 3 个术语的数字是 959 - 必须运行我的算法到 1000 个数字才能找到它。它是由 6 + 953 (primatic) 求和的，无论你如何拆分 6 它仍然是 3 项。

如何找到总和为给定数字的最少数量的灵长类动物

how to find the minimum number of primatics that sum to a given number

c++

primes

dynamic-programming

动态编程方法

工作示例