题目来源： 

基准时间限制：4 秒 空间限制：131072 KB 分值: 40 

 收藏

 取消关注

两个士兵正在玩一个游戏，游戏开始的时候，第一个士兵为第二个士兵选一个正整数n。然后第二个士兵要玩尽可能多的轮数。每一轮要选择一个正整数x>1，且n要是x的倍数，然后用n/x去代替n。当n变成1的时候，游戏就结束了，第二个士兵所得的分数就是他玩游戏的轮数。

为了使游戏更加有趣，第一个士兵用 a! / b! 来表示n。k!表示把所有1到k的数字乘起来。

那么第二个士兵所能得到的最大分数是多少呢？

Input

单组测试数据。第一行包含一个整数t (1 ≤ t ≤ 1，000，000)，表示士兵玩游戏的次数。接下来t行，每行包含两个整数a,b (1 ≤ b ≤ a ≤ 5，000，000)。

Output

对于每一组数据，输出第二个士兵能拿到的最多分数。

Input示例

23 16 3

Output示例

25

要求的就是素数因子的个数，相同的素数因子个数也要相加。然后求前缀和。

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #pragma warning(disable:4996)using namespace std;#define maxn 5000003int val[maxn + 1];int sum[maxn + 1];int prime[maxn + 1];void init(){ memset(sum, 0, sizeof(sum)); memset(prime, 0, sizeof(prime)); int i, j, temp; prime[1] = 0; for (i = 2; i <= maxn; i++) { if (!prime[i]) { for (j = i; j <= maxn; j=j+i) { temp = j; while (temp%i==0) { temp = temp / i; sum[j]++; } prime[j] = 1; } } } for (i = 1; i <= maxn; i++) { sum[i] = sum[i] + sum[i - 1]; }}int main(){ //freopen("i.txt","r",stdin); //freopen("o.txt","w",stdout); int test, a, b, i; long long res; scanf("%d", &test); init(); while (test--) { scanf("%d%d", &a, &b); printf("%d\n", sum[a]-sum[b]); } //system("pause"); return 0;}
         
        
       
      
     
    

版权声明：本文为博主原创文章，未经博主允许不得转载。