给我一个大号n我需要找出它是否可以表示为 K 个质数之和。
例 9 可以表示为 3 个质数之和为 2+2+5。
我正在尝试使用子集和的变体，但数字太大，无法生成所有素数。
问题来自当前HackerRank contest .限制是 1 <= n, K <= 10^12
最佳答案
对于 K = 1，如果 N 是素数，答案显然是"is"
对于 K = 2，根据 Goldbach conjecture , 已验证 N 高达 10^18 左右，如果 N 是偶数且 N >= 4 或 N - 2 是素数，则答案为"is"。
有趣的情况是 K = 3。显然，如果 N < 6，答案是否定的，因为可以表示为三个素数之和的最小数是 2 + 2 + 2 = 6。 如果 N >= 6，则 N - 2 或 N - 3 是偶数且 >= 4，因此我们可以再次应用哥德巴赫猜想。
所以对于 K = 3，如果 N >= 6，答案是"is"。
通过归纳法(提示:只需使用 K - 素数 2 的 3 倍)，我们可以证明对于 K >= 3，答案是"is" iif N >= 2*K，所以只有 K = 1 的情况和 K = 2 是非常重要的，只需要一个简单的素数检查，例如通过Miller–Rabin在 O(log^4 N) 中。
编辑:作为奖励，这个证明还给出了一个构造性算法来输出分区。我们使用多个 2 和一个 3 来得到 K = 2。棘手的 K = 2, N even 情况并不像看起来那么难:我们从 computational verification 知道哥德巴赫猜想，对于 N >= 12，存在一个哥德巴赫分区，其素数 < 5200 左右。这样的质数少于 700 个，因此我们可以在合理的时间内检查所有这些质数。
关于algorithm - 将数字表示为质数之和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23789802/