Luogu P2618 数字工程

DP

根据题目下面的提示&说明，我们就能知道做这个题的大体思路：先求出来每一个数的素数因子，然后就开始DP。

求素数因子的方法就是用类似于欧拉筛的操作，倘若一个数一直都没有被筛到过，那么ta就是一个素数，然后我们就可以用ta来继续筛其它的数，并且我们只用筛ta的倍数，因为只有ta的倍数才含有这个素因子，被筛到的数一定要及时打上标记 不要问我为什么那么我们需要开多大的数组来记录素因子呢？其实只用23左右就可以了，因为\(2^{20}=1048576>10^6\),所以开23足够。

最后就是DP部分了，只要考虑两种情况，由\(i-1\)或\(i/prime_i\)转移过来的，答案取个\(min\)就好了，还有本题的输入有点坑，具体的解决方案就是这样写就珂以了：

while(scanf("%d",&n)!=EOF)printf("%d\n",f[n]);

最后献上我丑陋的代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000000,M=1000010;
int n;
int yz[M][23],num[N],f[M];
bool vis[M];
void yych()
{
    for(int i=2;i<=N;++i)
    if(!vis[i])
    for(int j=i;j<=N;j+=i)
    vis[j]=1,yz[j][++num[j]]=i;//注意vis 
    
    for(int i=2;i<=N;++i)//DP
    {
        f[i]=f[i-1]+1;
        for(int j=1;j<=num[i];++j)f[i]=min(f[i],f[i/yz[i][j]]+1);
    }
}
int main()
{
    yych();
    while(scanf("%d",&n)!=EOF)printf("%d\n",f[n]);//scanf存在返回值，当不再输入的时候就会返回EOF 
}