自动搬运

查看原文

来自洛谷，原作者为

	Leianha 万般皆下品，惟有透彻高

搬运于2025-08-24 21:39:43，当前版本为作者最后更新于2019-09-17 20:40:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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 
}