数字是质数部分

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次。3也一样，得到2发生）。之后，遍历数组并选择一个“ leader”来确定我们在数组中的距离。我知道解释太可怕了，所以这是代码：

#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

Answer 1

动态编程是您的朋友。

考虑数字27。

如果7具有5个结果，而20具有732个结果，则您知道27至少具有（732 * 5）个结果。您可以使用两个变量系统（1 + 26、2 + 25
…等），并随便使用预先计算的值。您不必重新计算25或26，因为您已经进行了计算。