A friend of mine asked me a problem, but I couldn't find a good way to solve.
The problem: N is the number of ways to represent number X as sum of prime numbers. For example, if X is 10, N is 5 because (5 + 5) = (2 + 2 + 3 + 3) = (2 + 3 + 5) = (2 + 2 + 2 + 2 + 2) = (3 + 7) = 10. N is given to you. Compute X. (If there are more than one answer, you can output any of them.)
Do you have any idea?
I think you forgot (3+7)=10. So N is 5. Am I wrong?
You're right. I've fixed it now.
I thought something,but maybe is wrong. But I will give it a try. If x=10,you can find all primes that are less than 10. In our example (2,3,5,7). After you will divide each one with 10,to see how many times each number fit to 10. So 10/2=5, 10/3=3.333=(int)3 , 10/5=2 , (int)10/7=1. So we have times=(5,3,2,1). Now you could make a string,that has five of 2,three of 3,etc.... For example: str="22222333557". After you can permute this string,and with 0(N) for each permutation,to add +1,if a sum makes us 10.
I am not sure for that,but I gave it a try as I said :P. (I think better coders than me,will give better answers).
If N is not too big (e.g. around 10000), you can use dynamic programming. let dp[N][K] be the number of ways representing N as sum of first K prime numbers.
Yea,that is much better than mines. :P
Firstly take prime numbers in one array, and solve it by using dp-knapsack.