LC LCP 14. 切分数组

link

 解法：

maxprime存一个数的最大质因数，primeMin[i] 一个数n的质因数存在i，以n结尾所分得的最小子数组数。

class Solution {
public:
    static const int maxn=1000000;
    int maxprime[maxn+1];
    int primeMin[maxn+1];
    void primetable(){
        for(int i=2;i<=maxn;i++){
            maxprime[i]=1;
        }
        vector<int> primes;
        for(int i=2;i<=maxn;i++){
            if(maxprime[i]==1){
                for(int j=i;j<=maxn;j+=i){
                    maxprime[j]=i;
                }
            }
        }
    }

    int splitArray(vector<int>& nums) {
        primetable();
        int n=nums.size();
        vector<int> dp(n+1,0);
        for(int i=0;i<n;i++){
            int num=nums[i];
            int idx=0;
            dp[i+1]=1+dp[i];
            while(num!=1){
                int prime=maxprime[num];
                if(primeMin[prime]==0) primeMin[prime]=dp[i]+1;
                else primeMin[prime]=min(primeMin[prime],dp[i]+1);
                dp[i+1]=min(dp[i+1],primeMin[prime]);
                num/=prime;
            }
        }
        return dp[n];
    }
};