思路

士兵二应该只用质数，假设最优解中用了一个合数，则将合数替换成它的质因子可以整除的次数更多，这与该方案是最优解矛盾。

记 $f(i)$ 为 $i$ 的质因子个数（质因数分解中的每个质因子指数之和），$g(i)$ 为 $i!$ 的质因子个数。若 $p$ 是 $i$ 质因子，则 $f(i) = f(i / p) + 1$，且 $g(i) = g(i - 1) + f(i)$，以上递推都可在线性筛中完成。由于 $b! \mid a!$，若 $p$ 是 $b!$ 的质因子，且个数为 $k$，则 $p$ 一定是 $a!$ 的质因子，且个数不小于 $k$，因此答案是 $g(a) - g(b)$。换一种理解方式，由于 $g(i)$ 是 $f(i)$ 的前缀和，且

$$ n = \frac{a!}{b!} = (b+1)(b+2)\cdots(a-1)a $$

因此 $n$ 的质因子个数是 $f(i)$ 的区间和 $\sum_{i = b+1}^{a} f(i) = g(a) - g(b)$。

时间复杂度 $O(n)$。

#include <iostream>

#define endl "\n"

using namespace std;

constexpr int N = 5000010;

int prime[N], n;
int f[N], g[N];

void init() {
  for (int i = 2; i < N; i++) f[i] = 1;
  for (int i = 2; i < N; i++) {
    if (f[i] == 1) prime[n++] = i;
    for (int j = 0; prime[j] <= (N - 1) / i; j++) {
      f[i * prime[j]] = f[i] + 1;
      if (i % prime[j] == 0) break;
    }

    g[i] = g[i - 1] + f[i];
  }
}

void solve() {
  int a, b;
  cin >> a >> b;
  cout << g[a] - g[b] << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  init();

  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}