如何将一个数字表示为4个质数的总和？ [英] how to represent a number as a sum of 4 primes?

问题描述

这是问题所在（四个素数的总和）指出：

Here is the problem (Summation of Four Primes) states that :

输入的每一行都包含一个整数N（N <= 10000000）。这是您必须表示为四个素数之和的数字

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

样本输入：
24
36
46
< br>

Sample Input:
24
36
46

示例输出：
3 11 3 7
3
7 13 13
11 11 17 7

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

我很快就想到了这个主意

This idea comes to my mind at a first glance

• 查找N以下的所有素数


• 查找带有整数分区问题（背包）的列表长度（.length = 4）

但是我认为这种算法的复杂度非常差。这个问题也看起来像哥德巴赫的s_conjecture
。如何解决此问题？

but complexity is very bad for this algorithm I think. This problem also looks like Goldbach's_conjecture more. How can I solve this problem?

推荐答案

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

This problem has a simple trick. You can express all numbers as 3+2 + "summation of two primes" or 2 + 2 + "summation of two primes" depending on parity of the number.

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

for the "summation of two primes", use Goldbach's Conjecture.

这篇关于如何将一个数字表示为4个质数的总和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！