Prime nos

[prat007]

Hye Guys

I have been working on this problem for too long...Would be really glad if u all can throw some light on how to go about this problem..

thnx in advance

PROB:

Express a given number as a summation of 4 positive primes.
Time limit of execution is 3.00 seconds.

Implement method/function which follows given signatures :


void prime_sum(int n,int sol[ ]);

The input contains one integer number N (N<=100000). This number you will have to express as a summation of 4 primes and an array of interger where you have to store all 4 numbers.
If summation is not possible then just fill first 4 entries of array as -1.

[KrishnaV]

First you need to store all the primes less than 100000 in an array or a binary-search-tree.

I'll give you a hint - "Any even number > 2 can be expressed as a sum of two prime numbers"
Now, to generate two primes that add to a given number (P), you select one prime (x) at a time from the array/bst you created and do a binary search for the other number (P-x) for a O(n logn) time. You can even do a linear time search by keep indexes to lowest and highest values of the array and sliding them right and left by comparing the sum until you either find the sum or exhaust the array

The trick is to reduce your problem to the problem of finding two primes that sum up to an even number.
I'll let you try that.

[prat007]

Thnx a lot man...but could you plz help me out write the function....

[KrishnaV]

sure I or anyone can help. if you post your solution, I'll tell you whats wrong with it if there's anything wrong.

[abhigrawal]

@KrishnaV
prat007 is selected for further rounds in General electricals......so plzz do not help such ppl...
because it is a contest that is going and it is unethical from your side to help such people.....