Express any number as the sum of four prime numbers

Question

I was give a problem to express any number as sum of four prime numbers.

Conditions:

• Not allowed to use any kind of database.
• Maximum execution time : 3 seconds
• Numbers only till 100,000
• If the splitting is NOT possible, then return -1

What I did :

1. using the sieve of Eratosthenes, I calculated all prime numbers till the specified number.

2. looked up a concept called Goldbach conjecture which expresses an even number as the summation of two primes.

However, I am stuck beyond that. Can anyone help me on this one as to what approach you might take?

The sieve of Eratosthenes is taking two seconds to count primes up to 100,000.

Answer 1

You could still be ok with time. Due to the Goldbach conjecture, Every even Number greater or equal 8 can be expressed as the sum of 2,2, and two further primes. Every odd number greater or equal 9 can be expressed as the sum of 2,3 and two further primes. It shouldn't take too long to figure out the primes.

Edit: Actually, you could speed this up significantly: For any even Number N, find the largest prime that is less or equal N-7 and choose that prime and 3, then look for two further primes to suit your sum. For any odd Number N, find the largest prime greater or equal N-6 and choose it and two, then again choose two primes.