why my code is getting time excedded in "decrease to zero" problem

Trying to solve hackerrank problem.

You are given Q queries. Each query consists of a single number N. You can perform 2 operations on N in each move. If N=a×b(a≠1, b≠1), we can change N=max(a,b) or decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. could you suggest how can I improve my code?

int downToZero(int n) {
int dp[n+1];
dp[0]=0;dp[1]=1;dp[2]=2;dp[3]=3;
for(int i=4;i<=n;i++)
{
    dp[i]=dp[i-1]+1;
    for(int j=2;j*j<=i;j++)
    {
        if(i%j==0)
        {
            int fac=max(j, i/j);
            dp[i]=min(dp[i], dp[fac]+1);
        }
    }

}
return dp[n];

}