我该如何找到一个数可以被表示为质数之和的方式数量？

Question

质数求和

数字7可以用5种质数之和的方式表示：

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

编写一个程序，计算数字n可以用多少种质数之和的方式表示。您可以假设n是0-100之间的数字。您的程序应在不到一秒钟的时间内打印出答案。

示例1：
输入数字：7 结果：5

示例2：
输入数字：20 结果：732

示例3：
输入数字：80 结果：10343662267187

我已经花了几个小时来解决这个问题。我无法从 (n-1) 中得到 n。以下是通过树搜索得到的前 30 个数字的总和。

0 0 0 1 2 2 5 6 10 16 19 35 45 72 105 152 231 332 500 732 1081 1604 2351 3493 5136 7595 11212 16534 24441

我认为我在找到最长链的问题上有些进展，比如 7 = 5+2，而且我知道五可以写成 5、3+2 或者 2+3，但是我需要处理重复的 2+3+2 替换。

- ahathoor

---

但是因式分解与乘法有关，而不是求和。 - ahathoor

这绝不是https://dev59.com/MnRC5IYBdhLWcg3wJNcN的副本。 - Eamon Nerbonne

有点讽刺的是，它现在实际上成为了新问题的副本：https://dev59.com/VW3Xa4cB1Zd3GeqPd196 - Eamon Nerbonne

Answer 1

请查阅动态规划，特别是维基百科页面和其中斐波那契数列的示例，并思考如何将其应用于您在此处遇到的问题。

- Kevin

---

我正在看着它。但是你看过我发布的数字序列吗？ - ahathoor

我正在写这个来进行再次核对，但我认为动态规划应该考虑重复。 - Kevin

经过进一步的工作/反思，这可能不是正确的方法。如果您获得所有唯一的和集合（这应该不难，我认为最坏情况下是n^2？），则可以数学计算每个集合的排列数量。 - Kevin

Answer 2

好的，这是一个复杂的问题。您正在询问如何编写分区函数的代码；我建议您先了解分区函数本身。接下来，您应该查看计算分区的算法。这是一个复杂的主题，在这里有一个起点...... 分区问题是[NP完全] --- 这个问题已经在这里提出并回答，这也可能帮助您开始使用算法。

- Ahmed Masud

---

那么如果它是NP问题，这是否意味着老师基本上在“应该少于一秒钟”的部分里戏弄我？ - ahathoor

100这个数非常小，可以在一秒钟内轻松完成。 - Daniel Fischer

啊，这变得非常有趣了 穿上维基百科潜水服 - ahathoor

我已经包含了解决方案的链接...请参考[此处已提问并回答]。 - Ahmed Masud

我认为它做的事情和我目前编码的东西一样，当n~40时需要超过一秒的时间。 - ahathoor

不，它完全做了另一件事。谢谢，我会分析它。 - ahathoor

Answer 3

有几种选择。既然你知道这个数字在0-100之间，显而易见的方法是：作弊，简单地创建一个数组并填入数字。

另一种方法是使用循环。你需要找出100以下的所有质数，因为小于100的数字不能用大于100的质数之和表示。例如，99不能表示为2和任何大于100的质数之和。

你还需要知道的是：偶数的和的最大长度是该数字除以2。因为2是最小的质数。对于奇数，最大长度是（数字-1）/2。

例如： 8 = 2 + 2 + 2 + 2，因此和的长度为4
9 = 2 + 2 + 2 + 3，因此和的长度为4

如果你想要更好的性能，你可以通过使用GPGPU来作弊，这将显著提高性能。

然后是洗牌方法。如果你知道7 = 2 + 2 + 3，那么你也知道7 = 2 + 3 + 2。要做到这一点，你需要一种计算不同洗牌可能性的方法。你可以存储可能性的组合或在编写循环时记住它们。

这里是一个相对蛮力的方法（使用Java）：

int[] primes = new int[]{/* fill with primes < 100 */};
int number = 7; //Normally determined by user
int maxLength = (number % 2 == 0) ? number / 2 : (number - 1) / 2; //If even number maxLength = number / 2, if odd, maxLength = (number - 1) / 2
int possibilities = 0;    

for (int i = 1; i <= maxLength; i++){   
    int[][] numbers = new int[i][Math.pow(primes.length, i)]; //Create an array which will hold all combinations for this length
    for (int j = 0; j < Math.pow(primes.length, i); j++){ //Loop through all the possibilities
        int value = 0; //Value for calculating the numbers making up the sum
        for (int k = 0; k < i; k++){
            numbers[k][j] = primes[(j - value) % (Math.pow(primes.length, k))]; //Setting the numbers making up the sum
            value += numbers[k][j]; //Increasing the value
        }
    }
    for (int x = 0; x < primes.length; x++){
        int sum = 0;
        for (int y = 0; y < i; y++){
            sum += numbers[y];
            if (sum > number) break; //The sum is greater than what we're trying to reach, break we've gone too far
        }
        if (sum == number) possibilities++;
    }
}

我知道这很复杂。我会尝试用类比来解释。把它想象成一个组合锁。你知道最大的轮数，因此需要尝试，这就是“i”循环。接下来，你通过每个可能性（“j”循环）然后设置单个数字（“k”循环）。在“k”循环中的代码用于从当前可能性（j的值）到实际数字的转换。在输入了该数量的所有组合之后，计算是否有任何正确的组合，如果有，则增加可能性的数量。

如果我的代码有任何错误，我提前向您道歉。

- Boude