how to represent a number as a sum of 4 primes ?
Here is the problem ([Summation of Four Primes][1]) 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:<br> 24 <br> 36 <br> 46
> <br>
> 
>   Sample Output: <br> 3 11 3 7 <br> 3
> 7 13 13 <br> 11 11 17 7 <br>

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][2]
more. How can I solve this problem?


  [1]: http://acm.uva.es/p/v101/10168.html
  [2]: http://en.wikipedia.org/wiki/Goldbach's_conjecture
how to represent a number as a sum of 4 primes ?
===

Here is the problem ([Summation of Four Primes][1]) 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:<br> 24 <br> 36 <br> 46
> <br>
> 
>   Sample Output: <br> 3 11 3 7 <br> 3
> 7 13 13 <br> 11 11 17 7 <br>

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][2]
more. How can I solve this problem?


  [1]: http://acm.uva.es/p/v101/10168.html
  [2]: http://en.wikipedia.org/wiki/Goldbach's_conjecture