Search code examples
algorithmmathprimesnumber-theory

how to represent a number as a sum of 4 primes?

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

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

This idea comes to my mind at a first glance

  • Find all primes below N
  • Find length of list (.length = 4) with Integer Partition problem (Knapsack)

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?

Solution

  • 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.