```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
const int maxn =1e6+5;
struct node{int x,c;};
queue<node> q;
//预处理出每个数的质因子，再BFS暴力
int n,d[maxn][25],vis[maxn],prime[maxn],cnt[maxn],ans[maxn];//cnt 每个数的质因子个数
int read(){
char ch=getchar(); int f=1,a=0;
while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch)){a=a*10+ch-'0'; ch=getchar(); }
return a*f;
}
void BFS(){
while(!q.empty()) q.pop();
memset(vis,0,sizeof(vis));
q.push((node){n,0}); vis[n]=1;
while(!q.empty()){
node now=q.front(); q.pop();
if(now.x==1){
cout<<now.c;
return ;
}
if(!vis[now.x-1]) vis[now.x-1]=1,q.push((node){now.x-1,now.c+1});
for(int i=1;i<=cnt[now.x];i++)
if(!vis[now.x/d[now.x][i]])
vis[now.x/d[now.x][i]]=1,q.push((node){now.x/d[now.x][i],now.c+1});
}
}
int main(){
for(int i=2;i<=1000000;i++){
if(!prime[i]){
d[i][++cnt[i]]=i;
for(LL j=i*2;j<=1000000;j+=i){
prime[j]=1;
d[j][++cnt[j]]=i;//6 :2 3 不从i*i开始会炸，并且会漏掉素因子
//i==3时从9开始 6的会漏掉
}
}
}
/*for(int i=2;i<=100;i++){
cout<<i<<" ";
for(int j=1;j<=cnt[i];j++) cout<<d[i][j]<<" ";
cout<<endl;
}*/
while(cin>>n) BFS();
return 0;
}
```@[山雨木子](/space/show?uid=38522)
by 山雨木子 @ 2018-10-31 22:13:57
已解决
没打换行
by 山雨木子 @ 2018-11-01 17:40:53