一些因为它是素数的部分(A number as it's prime number part

我必须打印，你可以代表一个给定的数字，因为它是素数的部分方式的数量。

让我澄清一下：比方说，我一直在考虑这个号码7。现在，首先，我必须找到所有的质数小于7，这是2,3和5。现在，在多少个方式我总结这些数字（我可以使用同一个号码多次我想），这样的结果等于7？例如，7号有五个方面：

我完全失去了与这个任务。首先我想我使可用元素的数组像这样：{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

SO ...任何想法？这是一个组合子问题吗？我不需要的代码，只是一个想法。我还是个新手，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，因为你已经做了他们。

Answer 2:

您正在搜索的概念是一个数字的“黄金分割”。若干第分区是添加数字以到达目标的一种方式; 例如，1 + 1 + 2 + 3是7.一个分区如果所有的加数是素数，则该分区是一个素数的分区。

我觉得你的例子是错误的。数字7通常被认为是具有3个原分区：2 + 2 + 3，2 + 5和7所述加数的顺序并不重要。在数论，计数主要分区功能是卡帕，所以我们会说卡帕（7）= 3。

卡帕的通常计算分两部分进行。第一部分是计算一个数字的素因子之和的函数; 例如，42 = 2·3·7，所以sopf（42）= 12。需要注意的是sopf（12）= 5，因为求和是在只有一个号码的不同因素的影响，所以即使12 = 2·2·3，只有一个2被包括在总和的计算。

鉴于sopf，有一个长的公式来计算卡帕; 我给它胶乳形式的，因为我不知道怎么在这里输入：\卡帕（N）= \压裂{1} {N} \左（\ mathrm {} sopf（N）+ \ sum_ { J = 1} ^ {N - 1} \ {mathrm} sopf（J）\ CDOT \卡帕（NJ）\右）。

如果你真的想要的分区的列表，而不是仅仅计数，有一个动态编程解决方案，@corsiKa指出。

我在详细讨论黄金分割我的博客，包括源代码同时生产的数量和名单。

Answer 3:

下面是它采用动态编程像corsiKa建议，但不使用他所描述的算法的高效实现。

简单地说：如果n是经由可达k不同的路径（包括单步之一，如果它存在），和p是素数，则我们构建k路径n+p通过附加p向所有路径n 。考虑所有这些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;
}