一个数字,因为它是素数部分

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,得到两个出现次数).之后,循环遍历数组并选择一个'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,因为您已经完成了它们.