问一道acm的题,提交时老实说超时.

你的算法的时间复杂度太高了,对于每个区间的每个数字都要处理,而且还要给这个数字进行素数分解,那么时间复杂度为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,一秒内就能跑完了