algorithm - 如何将数字表示为 4 个素数之和？

Question

问题 (Summation of Four Primes) 指出:

The input contains one integer number N (N<=10000000) in every line. This is the number you will have to express as a summation of four primes

Sample Input:
24
36
46

Sample Output:
3 11 3 7
3 7 13 13
11 11 17 7

我第一眼就想到了这个想法

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

但我认为这种算法的复杂性非常糟糕。这个问题也看起来像 Goldbach's_conjecture更多的。我该如何解决这个问题？

Answer 1

这个问题有一个简单的技巧。您可以将所有数字表示为 3+2 +“两个素数之和”或者2 + 2 + “两个素数之和”取决于数字的奇偶性。

对于“两个素数之和”，使用哥德巴赫猜想。