Express any number as the sum of 4 prime numbers [Doubts]

Posted by WarDoGG on Stack Overflow See other posts from Stack Overflow or by WarDoGG
Published on 2010-04-30T11:29:47Z Indexed on 2010/04/30 12:07 UTC
Read the original article Hit count: 115

Filed under:
|
|
|

I was give a problem to express any number as sum of 4 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 2 primes.

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

The sieve of eratosthenes is taking 2 seconds to count primes till 100,000 :(((

© Stack Overflow or respective owner

Related posts about math

Related posts about c++