use*_*974 2 algorithm dynamic-programming
给我一个很大的数字n,我需要找到它是否可以表示为K素数的总和.
Ex 9可以表示为3素数之和为2 + 2 + 5.
我试图使用子集和的变化,但数量太大,无法生成所有素数.
问题来自当前的HackerRank比赛.限制是1 <= n, K <= 10^12
对于K = 1,答案显然是"是",如果N是素数
对于K = 2,根据Goldbach猜想,其验证N达到大约10 ^ 18,答案是"是",如果N是偶数且N> = 4或者如果N-2是素数.
有趣的情况是K = 3.显然,如果N <6,答案是"否",因为作为三个素数之和可表示的最小数是2 + 2 + 2 = 6.如果N> = 6,那么N - 2或N - 3是偶数且> = 4,因此我们可以再次应用Goldbach的猜想.
因此,对于K = 3,答案为"是",如果i> N = 6.
通过归纳(暗示:只使用K - 3倍于素数2),我们可以证明,对于K> = 3,答案是"是",如果N> = 2*K,那么只有K = 1和K = 2是非平凡的,只需要简单的素性检查,例如通过O(log ^ 4 N)中的Miller-Rabin.
编辑:作为奖励,此证明还提供了一个输出分区的建设性算法.我们用2和3来得到K = 2.棘手的K = 2,N偶然情况并不像它看起来那么难:我们从Goldbach猜想的计算验证得知,对于N> = 12,有一个Goldbach分区,素数<5200左右.这些素数不到700个,所以我们可以在合理的时间内检查它们.