我必须打印一些方法来表示给定数字,因为它是质数部分。
让我澄清一下:假设我得到了这个数字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;
}
这根本行不通。仅仅是因为背后的想法是错误的。以下是有关限制的一些详细信息:
另外,可以给出的最大数字是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
最佳答案
动态编程是您的 friend 。
考虑数字27。
如果7具有5个结果,而20具有732个结果,则您知道27至少具有(732 * 5)个结果。您可以使用两个变量系统(1 + 26、2 + 25 ...等),并随便使用预先计算的值。您不必重新计算25或26,因为您已经进行了计算。
关于c++ - 数字是质数部分,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14218882/