P2618 数字工程

题目描述

ACM实验室开启了一个数字工程项目，希望把正整数n通过一些特殊方法变成1。

可采用的方法有：（1）减去1；（2）除以它的任意一个素因子。 每操作一次消耗一个单位的能量。

问，把n变成1最少需要消耗多少能量？

输入输出格式

输入格式：

多组测试

对于每组测试，输入正整数n (1<=n<=1,000,000)

输出格式：

输出最少消耗的能量

#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
int dp[1000001],prime[1000001],pcnt=0,n;
bool bol[1000001];
int main()
{
    int j;
    for(int i=2;i<=1000000;i++)dp[i]=inf;
    bol[1]=1;
    for(int i=2;i<=1000000;i++)
    {
        if(!bol[i])
        {
            j=i+i;prime[++pcnt]=i;
            while(j<=1000000)
            {
                bol[j]=1;j+=i;
            }
        }
    }
    while(scanf("%d",&n)!=EOF)
        {
        if(dp[n]==inf)
        for(int i=1;i<=n;i++)
        {
            dp[i+1]=min(dp[i]+1,dp[i+1]);
            for(int j=1;j<=pcnt;j++)
            {
                if(i*prime[j]>n)break;
                dp[i*prime[j]]=min(dp[i*prime[j]],dp[i]+1);
            }
        }cout<<dp[n]<<endl;    
        }
}