Description
zyf最喜欢的数字是1！所以他经常会使用一些手段，把一些非1的数字变成1，并为此得意不已。他会且仅会的两种手段是：
1.把某个数m除以某个质数p——当然p必须能整除这个数，即m=m/p
2.把某个数m减1，即m=m-1
有一天他突发奇想，想把[a,b]区间中所有的数一个一个地变成1，这是一个巨大的无聊的工程，所以他想知道他最少得花多少操作才能达到目的。
Input
输入包含多组数据（1000组数据），EOF结束。
每组数据以两个整数开头：a，b(0<a<=b<=100000)，意义如题意描述。
每组数据以两个整数开头：a，b(0<a<=b<=100000)，意义如题意描述。
Output
每组数据输出一行，最少操作数。
Sample Input
2 3
3 5
11 12
3 5
11 12
Sample Output
2
4
3
4
3
问题分析：
要求出把a，b之间所有数变成1的最少步骤，肯定得计算出每个数字变成1的最少步骤。那么如何求出一个数字通过题中两种运算变成1的最小步骤呢？
分析到这，我们脑中肯定展现出一个树状结构出来，每个节点是当前的数字，而他可以有未知个孩子节点，包括减一操作以及除以的所有的素因子的操作。于是我们感觉到问题的复杂，求一个数字变成1的方法尚且这么复杂，还让求出最少步骤。即使算出来了，也很费时啊。
引用小平爷爷的一句话：没有调查就没有发言权！
1.其实认真想一下，一个数字的素因子是有限的，据2*3*5*7*11*13<100000<2*3*5*7*11*13*17可以判断100000以内的数字最多有6个素因子。所以我们的分支没有那么多。
2.不要忘了任何一个素数只需一步就可以变成1。100000以内大概有一万个素数，用素数筛选法计算出素数后，我们已经解决了一万个数字了。而且后面假设用递归或者动态规划也很容易的可以使用剪枝了。
3.计算n需要多少步骤时，其实是比较n-1,n/p……（p为素因子）中最小步骤的然后加一即可。
到此大概算法已经有了。
解法一：果断可以递归吗，最朴素的算法没有优化，需要10秒左右才可以算完100000以内的所有数。
解法二：在素数筛选后把素数弄到素数表中存起来，减少判断素数的时间，同时去掉函数的递归调用，因为可以从小的数往大的数算，也即是迭代式的。效率提高到3秒。
int search_deep(int num){
if(data[num] != 0){
return data[num];
} else {
int temp = data[num - 1] + 1;
int i = 0;
/* 解法一
for(i = num / 2; i > 1; i--){
if(!prime[i] && num % i == 0 && search_deep(num / i) + 1 < temp){
// temp = search_deep(num / i) + 1;
temp = data[num / i] + 1;
}
}
*/
// 解法二
for(i = 1; prime_array[i] <= num / 2; i++){
if(temp <= 2)
break;
if(num % prime_array[i] == 0 && data[num / prime_array[i]] + 1 < temp){
temp = data[num / prime_array[i]] + 1;
}
}
return temp;
}
return 0;
}
解法二做了大量优化已经达到了3秒的时间效率，可是还是太慢，其实主要原因的总是从最小素数开始判断是否为素因子，感觉接近1的速度就会慢下来。如果能从最大的素因子开始判断就更好了，可是似乎没什么解决办法。罢了。
解法三：类似于素数筛选法，著名的素数筛选法应该都知道不用解释。那么也可以利用这个思想来解决这个问题。如果数n变成1的步骤为x，那么n乘以任何一个素数的步骤都是x+1。这个思想似乎是真正的迭代，先解决小问题，再解决大问题，速度要高很多！代码如下：
void generate(){
prime[1] = 1;
prime[2] = 0;
prime[3] = 0;
int i = 0;
int j = 0;
int k = 1;
for(i = 2; i < 100001; i++){
if(prime[i] == 0){
data[i] = 1;
for(j = 2; i * j < 100001; j++){
prime[i * j] = 1;
}
prime_array[k++] = i;
}
}
for(i = 2; i <= 100000; i++){
if(data[i - 1] + 1 < data[i])
data[i] = data[i - 1] + 1;
for(j = 1; j < k && 1.0 * i * prime_array[j] < 100001; j++){
if(data[i] + 1 < data[i * prime_array[j]] || data[i * prime_array[j]] == 0){
data[i * prime_array[j]] = data[i] + 1;
}
}
}
}
解法三的执行效率一下提高到了10ms左右！惊呼啊！主要是解法三的判断条件让程序去掉了很多没用的计算。