Question

问一道acm的题，提交时老实说超时。

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)，意义如题意描述。
Output
每组数据输出一行，最少操作数。
Sample Input
2 3
3 5
11 12
Sample Output
2
4
3
我的代码：
#include <stdio.h>
#include<math.h>
int judge(int n)
{
int i;
int k;
k=sqrt((double)n);
for(i=2;i<=k;i++)
{
if(n%i==0)
break;
}
if(i==k+1)
return 1;
else
return 0;
}
int main()
{
int a,b,k,i,n;
int judge(int x);
while(scanf("%d %d",&a,&b)!=EOF)
{
k=0;
for(i=b;i>=a;i--)
{
if(judge(i))
k++;
else
{
for(n=i-1;n>=a;n--)
{
k++;
if(judge(n))
{
k++;
break;
}
}

}

}

printf("%d\n",k);
}
}

Answer 1

你的算法的时间复杂度太高了，对于每个区间的每个数字都要处理，而且还要给这个数字进行素数分解，那么时间复杂度为1000 (case) * 100000 (b-a) * 100000 (i) = 10^13 那显然是不行的了。

给你下我的想法：
1.筛法筛出2-100000的所有素数，在用素数P筛去一个合数Q的时候，要将P记录下来，保存在a[Q]中(a[Q]=P) 算法复杂度为o( n * log log n )
2.筛完以后，用o(n)的算法从小到大计算出每个数拥有的质因数个数( 当i为合数时c[i]=c[i/a[i]]+1 而c[i/a[i]]在之前已算出) 算法复杂度为o( n )
3.构造sum数组记录c[0-i]的和放入sum[i] 算法复杂度为o( n )
4.对于询问a-b输出sum[b]-sum[a-1]即可 算法复杂度为o( case )

于是总复杂度为n log log n接近o (n)了 不会超过10^6，一秒内就能跑完了