1. 题目

传送门＝￣ω￣＝

2. 题解

跑一遍素数筛，筛出每个数字的所有质因数，存在数组里。
然后 $f(i)=min(f(i-1),f(i/p))+1$，$p$是 $i$的质因数。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,f[1000005],d[1000005][25],dc[1000005];
bool book[1000005];
int main()
{
    for(int i=2;i<=1000000;i++)
        if(!book[i])
            for(int j=i;j<=1000000;j+=i)
                book[j]=1,d[j][dc[j]++]=i;
    for(int i=2;i<=1000000;i++)
    {
        f[i]=f[i-1]+1;
        for(int j=0;j<dc[i];j++)f[i]=min(f[i],f[i/d[i][j]]+1);
    }
    while(~scanf("%d",&n))printf("%d\n",f[n]);
    return 0;
}