Develop a dynamic programming algorithm that calculates the minimum number of different primes that sum to x. Assuming the dynamic programming calculates the minimum number of different primes amongst which the largest is p for each couple of x and p.
Can someone help me? Thanks.
Well, if you name $f(n)$ your function, consider this: $ f(n)= \begin{cases} 1 &\text{if $n$ is a prime}\\ min_{1\leq k<n}\{f(n-k)+f(k)\} &\text{otherwise } \end{cases} $
Edit:
$ f(n,p)= \begin{cases} \infty &\text{if $p>n$}\\ 1 &\text{if $p=n$}\\ \min _{q<p, q \text{ prime}} f(n-p,q) &\text{otherwise } \end{cases} $