I FOUND POTENTIAL PROBLEM IN MY SOLUTION,SORRY FOR BOTHERING.
This Question can be solved using something like divide and conquer,
so if we want answer for n,first we will count the number of greatest power of primes below n, lets call count of them as y,
means, if n=7 than primes are 2,3,5,7,
and greatest power of those are 4,3,5,7,
so,first we will make these four number equal by lcm ,let it take x steps
than answer will be x+(n-y),as for (n-y) number it is going to take 1 step for each.
now,we want the x,
if we have y=4:-
eg:- 4,3,5,7
taking two step 12,12,35,35
again take two step 420 420 420 420
so for x=4 here as we took 4 steps.
so answer for 7 is 4+(7-4) that is 7, and the answer by this code is lesser than n+p-3 for many numbers.
so for finding x:
this can be used:-
cnt_dp[x]=cnt_dp[(int)ceil(x/2.0)]+cnt_dp[(int)floor(x/2.0)]+(int)ceil(x/2.0);
cnt_dp[2] will be 1 and cnt_dp[1]=0;
implemetation: