我必须打印出可以表示给定数字的方式数量,因为它是质数部分。
让我澄清一下:假设我得到了这个数字 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 也是如此,它有两个发生)。之后,遍历数组并选择一个“领导者”来确定我们在数组中的距离。我知道这个解释很糟糕,所以这里是代码:
#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