A number as it's prime number parts

Question

I have to print the number of ways you can represent a given number as it's prime number parts.

Let me clarify: Let's say I have been given this number 7. Now, first of all, I have to find all the prime numbers that are less than 7, which are 2, 3 and 5. Now, in how many ways can I summarize those numbers (I can use one number as many times I want) so that the result equals 7? For example, number 7 has five ways:

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

I'm totally lost with this task. First I figured I'd make an array of usable elements like so: { 2, 2, 2, 3, 3, 5 } (7/2 = 3, so 2 must appear three times. Same goes with 3, which gets two occurences). After that, loop through the array and choose a 'leader' that determines how far in the array we are. I know the explanation is horrible, so here's the code:

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

This simply doesn't work. Simply because the idea behind it is wrong. Here's a little details about the limits:

• Time limit: 1 second
• Memory limit: 128 MB

Also, the biggest number that can be given is 100. That's why I made the array of prime numbers below 100. The result grows very fast as the given number gets bigger, and will need a BigInteger class later on, but that's not an issue.

A few results known:

Input    Result

7        5
20       732
80       10343662267187

SO... Any ideas? Is this a combinatory problem? I don't need code, just an idea. I'm still a newbie to C++ but I'll manage

---

Keep in mind that 3 + 2 + 2 is different than 2 + 3 + 2. Also, were the given number to be a prime itself, it won't be counted. For example, if the given number is 7, only these sums are valid:

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

Answer 1

Dynamic programming is your friend here.

Consider the number 27.

If 7 has 5 results, and 20 has 732 results, then you know that 27 has at least (732 * 5) results. You can use a two variable system (1 + 26, 2 + 25 ... etc) using the precomputed values for those as you go. You don't have to recompute 25 or 26 because you already did them.