problem:

Given the number n , find the smallest positive integer which has exactly n divisors.

can someone tell me a dp solution for it and the logic behind it?

problem:

Given the number n , find the smallest positive integer which has exactly n divisors.

can someone tell me a dp solution for it and the logic behind it?

Answer depends on constraint.

For n<=10^5, it can be done in O(n sqrt(n))

Start with 2 and store its no of divisors in dp[2].

for any number you can calculate its no of divisors in Sqrt(n).

For any n, iterate from i=2 to sqrt(n), add dp[i] +dp[n/i] to dp[n] if n%i==0. Again add 2 for i=1 and i=n. Also you have to check if n is perfect square or not