首先我们要注意到，第二名士兵应该只选择质数。如果他选择了一个合数 $x = p \times q$，他可以先选 $p$ 再选 $q$，从而获得更高的得分。因此，我们的任务实际上是找出 $n$ 质因数分解中质因子的总个数（计重数）。

现在我们要注意到，数 $a! / b!$ 的质因数分解等价于 $(b+1) \times (b+2) \times \dots \times (a-1) \times a$ 的质因数分解。

我们需要计算从 $2$ 到 $5\,000\,000$ 每个数的质因子总个数。

首先，使用埃拉托色尼筛法找出每个数的一个质因子。然后，利用以下递推公式计算每个数 $a$ 的质因子总个数：

$$\text{primefactors}[a] = \text{primefactors}[a / \text{primedivisor}[a]] + 1 $$

当我们得到所有这些数后，可以使用前缀和，然后对于区间 $[b+1, a]$ 求和即可得到答案。

#include<cstdio>
int a[5555555];
int main()
{
	int i,j,k,n;
	for(i=2;i<=5000000;i++)
	{
		if(!a[i])for(j=1;i*j<=5000000;j++)for(k=i*j;k%i==0;k/=i)a[i*j]++;
		a[i]+=a[i-1];
	}
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&j,&k);
		printf("%d\n",a[j]-a[k]);
	}
}