一个数字可以表示为其素数因子的乘积，如何将其表示为若干个连续素数之和？

Question

我需要打印出如何将给定的数字表示为其质数部分的方式数量。

让我解释一下：假设我有数字7。首先，我需要找到所有小于7的质数，它们是2、3和5。现在，我可以用这些数字（我可以使用一个数字多次）以多少种方式总结这些数字，使得结果等于7？例如，数字7有五种方法：

2 + 2 + 3
2 + 3 + 2
2 + 5
3 + 2 + 2
5 + 2

我对这个任务完全不知所措。首先，我想创建一个可用元素的数组，如下所示：{2, 2, 2, 3, 3, 5}（7/2 = 3，因此2必须出现三次。同样的道理适用于3，它出现两次）。之后，循环遍历数组并选择一个“领导者”，确定我们在数组中的位置。我知道这个解释很糟糕，所以这里是代码：

#include <iostream>
#include <vector>

int primes_all[25] = {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};

int main()
{
    int number;
    std::cin >> number;

    std::vector<int> primes_used;

    for(int i = 0; i < 25; i++) {
        if(primes_all[i] < number && number-primes_all[i] > 1) {
            for(int k = 0; k < number/primes_all[i]; k++)
                primes_used.push_back(primes_all[i]);
        }
        else break;
    }

    int result = 0;

    for(size_t i = 0; i < primes_used.size(); i++) {
        int j = primes_used.size()-1;
        int new_num = number - primes_used[i];

        while(new_num > 1 && j > -1)
        {
            if(j > -1) while(primes_used[j] > new_num && j > 0) j--;

            if(j != i && j > -1) {
                new_num -= primes_used[j];

                std::cout << primes_used[i] << " " << primes_used[j] << " " << new_num << std::endl;
            }

            j--;
        }

        if(new_num == 0) result++;
    }

    std::cout << result << std::endl;

    system("pause");
    return 0;
}

这根本行不通。仅仅因为其背后的理念是错误的。以下是一些关于限制的细节：

• 时间限制: 1秒
• 内存限制: 128 MB

此外，能够给出的最大数字是100。这就是我创建小于100的素数数组的原因。随着给定的数字变大，结果会增长得非常快，需要用到BigInteger类，但这不是问题。

以下是一些已知的结果：

Input    Result

7        5
20       732
80       10343662267187

那么... 有什么想法吗？这是一个组合问题吗？我不需要代码，只需要一个想法。虽然我还是C++的新手，但我会应对。

---

记住，3 + 2 + 2和2 + 3 + 2是不同的。 另外，如果给定的数字本身是质数，则不计算在内。例如，如果给定的数字是7，则只有以下这些总和是有效的：

2 + 2 + 3
2 + 3 + 2
2 + 5
3 + 2 + 2
5 + 2
7 <= excluded

- Olavi Mustanoja

---

3 + 2 + 2 和 2 + 2 + 3 是否被视为不同的？ - corsiKa

是的。3 + 2 + 2 != 2 + 3 + 2 != 2 + 2 + 3。 - Olavi Mustanoja

这与哥德巴赫猜想有关。 - Mihai8

Answer 1

动态规划在这里是你的好帮手。

考虑数字27。

如果7有5个结果，20有732个结果，那么你知道27至少有(732*5)个结果。你可以使用一个两个变量的系统(1 + 26, 2 + 25 ...等)，在进行计算时使用预先计算好的值。因为已经计算过25或26了，所以你不需要重新计算它们。

- corsiKa

---

不要使用递归来完成这个任务，因为“你已经完成了它们”，而是使用循环从1开始构建总和，然后是2，直到你构建出目标数字的总和。通过重复使用旧值并在每一步中添加基本情况“单个质数”来计算新值。您不需要使用可用的数字集（primes_used）。 - leemes

这有点超出我的理解范围了。你能再解释一下吗？ - Olavi Mustanoja

这个提议通常情况下是行不通的；因为您忽略了质数的身份，而这很重要，因为不同的排序方式是有影响的。 - Eamon Nerbonne

你是不是想说“至少732 * 5个”结果？ - Peaceful

我是认真的吗？不，我不是。因为更正确，我应该把它放进去吗？是的，我应该。=) - corsiKa

Answer 2

你正在寻找的概念是一个数字的“质数分区”。一个数字的S分区是达到目标的一种加法方式；例如，1+1+2+3是7的一个分区。如果所有的加数都是质数，那么这个分区就是一个质数分区。

我认为你的例子是错误的。通常认为数字7有3个质数分区：2+2+3、2+5和7。加数的顺序并不重要。在数论中计算质数分区的函数是kappa，因此我们会说kappa(7)=3。

kappa的常规计算分为两部分。第一部分是计算一个数字的质因数之和的函数；例如，42=2·3·7，因此sopf(42)=12。请注意，sopf(12)=5，因为总和仅针对一个数字的不同因数，因此即使12=2·2·3，也只包括一个2在总和的计算中。

给定sopf，有一个冗长的公式来计算kappa；我会用LaTeX形式给出，因为我不知道如何在这里输入：\kappa(n) = \frac{1}{n}\left(\mathrm{sopf}(n) + \sum_{j=1}^{n-1} \mathrm{sopf}(j) \cdot \kappa(n-j)\right)。

如果您实际上想要一个分区列表，而不仅仅是计数，那么@corsiKa指出了一种动态规划解决方案。

我在我的博客中更详细地讨论了质数分区，包括生成计数和列表的源代码。

- user448810

---

这是一些很棒的信息。然而，在我的情况下，3 + 2 + 2与 2 + 3 + 2与 2 + 2 + 3是不同的。 - Olavi Mustanoja

这不是正常的方式。首先，你应该与你的导师明确询问要求的内容。然后，如果你真的想要你所说的，可以在谷歌上搜索“重复的质数分割”或“不同的质数分割”。无论如何，请注意你关于数字7的质数分割示例中漏掉了7本身，而7是质数，所以按照你的方法，制作数字7的分割有六种方式，而不是五种。 - user448810

抱歉，我以为我已经提到了。我会编辑问题描述。不过还是谢谢你指出路径 ：D - Olavi Mustanoja

谢谢您的回复。请与您的导师讨论质数分割的确切定义。我很难相信定义是您所描述的那样。 - user448810

他几乎立刻回复了我的电子邮件，而且是的，定义就像我描述的那样。 - Olavi Mustanoja

Answer 3

这里有一种高效的实现方法，它使用动态编程技术，就像corsiKa所建议的那样，但不使用他所描述的算法。

简单来说：如果通过k条不同路径（包括单步路径，如果存在的话）可以到达n，并且p是素数，那么我们将p添加到到达n的所有路径上，从而构造出到n+p的k条路径。考虑到所有这样的n<N，将产生一个详尽的有效路径列表到达N。因此，我们只需要总结发现的路径数量。

#include <iostream>

int primes_all[] = {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};

const int N_max = 85;
typedef long long ways;
ways ways_to_reach_N[N_max + 1] = { 1 };

int main()
{
    // find all paths
    for( int i = 0; i <= N_max; ++i ) {
        ways ways_to_reach_i = ways_to_reach_N[i];

        if (ways_to_reach_i) {
            for( int* p = primes_all; *p <= N_max - i && p < (&primes_all)[1]; ++p ) {
                ways_to_reach_N[i + *p] += ways_to_reach_i;
            }
        }
    }

    // eliminate single-step paths
    for( int* p = primes_all; *p <= N_max && p < (&primes_all)[1]; ++p ) {
        --ways_to_reach_N[*p];
    }

    // print results
    for( int i = 1; i <= N_max; ++i ) {
        ways ways_to_reach_i = ways_to_reach_N[i];

        if (ways_to_reach_i) {
            std::cout << i << " -- " << ways_to_reach_i << std::endl;
        }
    }

    return 0;
}

• 演示：http://ideone.com/xWZT8v

将typedef ways替换为大整数类型留给读者作为练习。

- Ben Voigt