如何将数字表示为4个素数的总和？

Question

这是问题(四个总和的总和)指出:

输入在每一行中包含一个整数N(N <= 10000000).这是您必须表示的四个素数的总和

样本输入:
24
36
46

样本输出:
3 11 3 7
3 7 13 13
11 11 17 7

乍一看,我想到了这个想法

• 找到N以下的所有素数
• 使用整数分区问题查找列表长度(.length = 4)(背包)

但我觉得这种算法的复杂性非常糟糕.这个问题看起来也像Goldbach's_conjecture .我怎么解决这个问题？

Answer 1

这个问题很简单.您可以将所有数字表示为3 + 2 +"两个素数的总和"或2 + 2 +"两个素数的总和",具体取决于数字的奇偶性.

对于"两个素数的总和",使用Goldbach的猜想.