p个质数的总和，并且结果必须少于p个质数。算法可以以某种方式“跳转”到数组中第一个满足p-1个质数之和不小于n的位置，从而跳过数组的“无聊”部分。当您从2个质数跳到单个质数并跳过一半的数组时，效果最为明显。 - Dialecticusp 个质数的位置也是最后一个位置。算法应该只是“跳跃”到下一个位置，并沿途递减 p。 - Dialecticus让我用C++编写一些代码，以使其更清晰，希望没有错误：
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
//Get the limit for the numbers
int MAX_N;
cin >> MAX_N;
//Compute the primes less or equal than MAX_N
vector<bool> is_prime(MAX_N + 1, true);
for (int i = 2; i*i <= MAX_N; ++i) {
if (is_prime[i]) {
for (int j = i*i; j <= MAX_N; j += i) is_prime[j] = false;
}
}
vector<int> prime;
for (int i = 2; i <= MAX_N; ++i) if (is_prime[i]) prime.push_back(i);
//Compute the prefixed sums
vector<ll> sum(prime.size() + 1, 0);
for (int i = 0; i < prime.size(); ++i) sum[i + 1] = sum[i] + prime[i];
//Get the number of queries
int n_queries;
cin >> n_queries;
for (int z = 1; z <= n_queries; ++z) {
int n;
cin >> n;
//Solve the query
bool found = false;
for (int i = 0; i < prime.size() and prime[i] <= n and not found; ++i) {
//Do binary search over the lenght of the sum:
//For all x < ini, [i, x] sums <= n
int ini = i, fin = int(prime.size()) - 1;
while (ini <= fin) {
int mid = (ini + fin)/2;
int value = sum[mid + 1] - sum[i];
if (value <= n) ini = mid + 1;
else fin = mid - 1;
}
//Check the candidate of the binary search
int candidate = ini - 1;
if (candidate >= i and sum[candidate + 1] - sum[i] == n) {
found = true;
cout << n << " =";
for (int j = i; j <= candidate; ++j) {
cout << " ";
if (j > i) cout << "+ ";
cout << prime[j];
}
cout << endl;
}
}
if (not found) cout << "No solution" << endl;
}
}
样例输入：
1000
5
12
20
28
17
29
示例输出：
12 = 5 + 7
No solution
28 = 2 + 3 + 5 + 7 + 11
17 = 2 + 3 + 5 + 7
29 = 29
123456789，我们立即知道它不可能是2（或4、6、8、10等）个连续质数的和，因此唯一需要考虑的候选项是3、5、7、9等质数。当然，反过来也一样：例如，给定12345678，它是偶数这个简单事实让我们立即排除了它可能是3、5、7或9个连续质数之和的可能性；我们只需要考虑2、4、6、8等质数序列。只有当我们得到足够多的质数时，才会违反这个基本规则，这时我们可以将2作为序列的一部分。我知道这个问题有点旧，但我不能克制回复先前答案中所做的分析。确实，已经强调了三个算法中所有提出的算法的运行时间基本上是线性的 n。但事实上，不难产生一个运行时间严格较小的 n 的算法。
为了看到如何做到这一点，让我们选择一个介于 1 和 n 之间的参数 K，并假设我们需要的质数已经被列成表格（如果它们必须从头开始计算，请参见下文）。然后，这是我们要做的，以搜索将 n 表示为 k 个连续质数之和：
第一部分涉及大质数的短和，需要进行O(log n)次操作来二分搜索一个接近n/k的质数，然后需要进行O(k)次操作来搜索其他k个质数（有几种简单的可能实现）。总体而言，这使得运行时间为
R_1=O(K^2)+O(Klog n)。
第二部分是关于小质数的长和，要求我们考虑连续质数的和p_1<\dots<p_k，其中第一个元素最多为n/K。因此，需要访问最多n/K+K个质数（可以通过素数定理的弱版本节省对数因子）。由于在算法中每个质数最多被访问O(1)次，因此运行时间为
R_2=O(n/K) + O(K)。
现在，如果 log n < K < \sqrt n，那么第一部分将运行 O(K^2) 次操作，第二部分将以 O(n/K) 运行。我们通过选择 K=n^{1/3} 来进行优化，从而使整体运行时间为
R_1+R_2=O(n^{2/3}).
如果素数未被列出
如果我们还需要找到素数，以下是我们的方法。
首先，我们使用 Erathostenes，在 C_2=O(T log log T) 次操作中找到所有小于 T 的素数，其中 T=O(n/K) 是算法第二部分访问的小素数的上限。
k<K，找到位于 n/k 周围的 O(k) 个质数。黎曼猜想暗示如果对于某个常数 c>0，y>c log x (k+\sqrt x)，则区间 [x,x+y] 中至少有 k 个质数。因此，我们需要先找到包含在以 n/k 为中心、宽度为 |I_k|= O(k log n)+O(\sqrt {n/k} log n) 的区间 I_k 中的质数。
使用筛法埃拉托色尼筛选区间 I_k 需要 O(|I_k|log log n) + O(\sqrt n) 次操作。如果 k<K<\sqrt n，则对于每个 k<K，时间复杂度为 C_1=O(\sqrt n log n log log n)。
综上所述，当
C_1+C_2+R_1+R_2时，时间复杂度最大化。
K = n^{1/4} / (log n \sqrt{log log n}).
选择这个公式可以实现次线性时间复杂度。
R_1+R_2+C_1+C_2 = O(n^{3/4}\sqrt{log log n}.
如果我们不假设黎曼猜想，我们将不得不在更大的区间上搜索，但最终仍然可以获得次线性时间复杂度。相反，如果我们对质数间隙做出更强的猜想，我们可能只需要在宽度为|I_k|=k (log n)^A的区间I_k上进行搜索，其中A>0。然后，我们可以使用其他确定性素性测试，而不是埃拉托斯特尼筛法。例如，假设您可以在O((log n)^B)操作中测试单个数字的素性，其中B>0。
那么您可以在O(k(log n)^{A+B})操作中搜索区间I_k。在这种情况下，最优的K仍然是K\approx n^{1/3}，除了对数因子之外，因此总复杂度为O(n^{2/3}(log n)^D，其中D>0。