收藏
关注两个士兵正在玩一个游戏，游戏开始的时候，第一个士兵为第二个士兵选一个正整数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示例
2
3 1
6 3
Output示例
2
5
思路:
一个大于1的整数肯定有一些质数组成，由于分数要最多，也就是每次除能够整除的质数。
这样问题就转化为了，求b+1,b+2...,a之间有多少个质数。由于一个合数由质数相乘构成，所以
可以在欧拉筛的时候，处理一下每个数有多少个质数组成。在处理一下前缀和。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<time.h>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1000000001
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = ;
int isnotprime[MAXN],prime[MAXN],cnt;
int a,b;
int ans[MAXN];
ll sum[MAXN];
void Init()
{
cnt = ;
memset(ans,,sizeof(ans));
memset(isnotprime,,sizeof(isnotprime));
for(int i = ; i <= MAXN - ; i++){
if(!isnotprime[i]){
ans[i] = ;
prime[cnt++] = i;
}
for(int j = ; j < cnt && 1LL * i * prime[j] < MAXN; j++){
isnotprime[i*prime[j]] = ;
ans[i*prime[j]] += ans[i] + ans[prime[j]];
if(i % prime[j] == )break;
}
}
sum[] = ;
sum[] = ;
for(int i = ; i <= MAXN - ; i++){
sum[i] = sum[i-] + ans[i];
}
}
int main()
{
int t;
Init();
cin >>t;
while(t--){
scanf("%d%d",&a,&b);
cout<<sum[a] - sum[b]<<endl;
}
return ;
}