determinism's blog

Prime Sum Problem
By determinism, 10 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you forgot (3+7)=10. So N is 5. Am I wrong?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're right. I've fixed it now.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Firstly take prime numbers in one array, and solve it by using dp-knapsack.

→ Reply