Я должен напечатать количество способов, которыми вы можете представить данное число в виде простых чисел.

Позвольте мне уточнить: допустим, мне дали это число 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 МБ

Кроме того, самое большое число, которое может быть дано, это 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