C++ 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2017-06-12

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> getyueshu(int n){
    vector<int> res;
     for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){
            res.push_back(i);
            if(n/i != i)
                res.push_back(n/i);
        }
    }
    return res;
}

int main(){
    int N,M;
    cin>>N>>M;
    vector<int> dp(M+1,M);
    dp[N]=0;
    for(int i=N;i<=M;i++){
        vector<int> path=getyueshu(i);
        for(int j=0;j<path.size();j++){
            if(i+path[j]<=M){
            	dp[i+path[j]]=min(dp[i]+1,dp[i+path[j]]);
            }
        }
    }
    if(dp[M]==M){
        cout<< -1;
    } 
    else{
        cout<< dp[M];
    }
    return 0;
}   

C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-06-15

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

std::vector<int> getDivisor(int num) {
	std::vector<int> ans;
	for (int i = 2; i <= sqrt((double)num); i++) 
		if (!(num % i)) {
			ans.push_back(i);
			if (num / i != i) 
				ans.push_back(num / i);
		}
	return ans;
}
int main()
{
	using namespace std;
	int n, m;
	while (cin >> n >> m) {
		vector<int> index(m + 1, 0);
		index[n] = 1;
		for (int i = n; i <= m; i++) {
			vector<int> divisors = getDivisor(i);
			if (!index[i])
				continue;
			else
				for (int j = 0; j < divisors.size(); j++) {
						if ((divisors[j] + i) <= m && index[divisors[j] + i] != 0)
							index[divisors[j] + i] = min(index[divisors[j] + i], index[i] + 1);
						else if ((divisors[j] + i) <= m)
							index[divisors[j] + i] = index[i] + 1;
				}
		}
		int ans = index[m] == 0 ? -1 : index[m] - 1;
		cout << ans << endl;
	}
	return 0;
}