离线处理。。。

先线性筛一遍。

直接预处理出所有答案。

注意要用push，用乘法，常数小。

 

#include 
     
      #include 
      
       #define N 1000001#define min(x, y) ((x) < (y) ? (x) : (y))int n, cnt;int f[N], prime[N];bool notpri[N];inline void init(){	int i, j;	notpri[0] = notpri[1] = 1;	for(i = 2; i < N; i++)	{		if(!notpri[i]) prime[++cnt] = i;		for(j = 1; i * prime[j] < N; j++)		{			notpri[i * prime[j]] = 1;			if(!(i % prime[j])) break;		}	}}int main(){	int i, j;	init();	memset(f, 127, sizeof(f));	f[1] = 0;	for(i = 1; i < N - 1; i++)	{		f[i + 1] = min(f[i + 1], f[i] + 1);		for(j = 1; j <= cnt && i * prime[j] < N; j++)			f[i * prime[j]] = min(f[i * prime[j]], f[i] + 1);	}	while(~scanf("%d", &n)) printf("%d\n", f[n]); 	return 0;}