[luoguP2618] 数字工程（DP）

传送门

离线处理。。。

先线性筛一遍。

直接预处理出所有答案。

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

#include <cstdio>
#include <cstring>
#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;
}