Help me with this problem

Find the minimum no of steps to reduce a number n to 0 using any of the following 2 operations:
1)Decrement number n by 1.

2)Determine a != 1 and b != 1 such that n=a*b and reduce n to max(a,b).

please help me with the logic and code.

for ex:for n=9, ans is 4.

I guess this can be done using dynamic programming.
Suppose the input is n.
then the answer has to be min(1+dp[n-1], 1 + dp[max(a,b)]) where dp[i] is the answer to n =i. You will have to write the base case for some of the initial cases. This cannot be performed for prime inputs though. For when n is prime, you cannot perform dp[max(a,b)]. So, the answer will have to be 1+ dp[n-1].

Would you mind providing the link to the question?

yes.Programming Problems and Competitions :: HackerRank

Looks like basically the same question as this one: