C++ 解法, 执行用时: 602ms, 内存消耗: 82728K, 提交时间: 2022-03-05 17:48:37

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
int main()
{
	ll n, m;
    int tt;
    for(cin>>tt;tt--;){
        
	scanf("%lld%lld", &n, &m);
vector<int>vis(n+1);
vector<int> cnt(21);
vector<int>b(m * 20);
	ll ans = 0;
	int ma = 0;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			int  c = 1;
			for (ll j = i; j <= n; j *= i, c++) {
				vis[j] = c;
			}
			cnt[c - 1]++;
		}
	}
	ll res = 0;
	for (int j = 1; j < 20; j++) {
		for (int i = j*2; i <= m * j; i += j) {
			if (!b[i])res++;
			b[i] = 1;
		}
		ans += res * cnt[j];
	}
	printf("%lld\n", ans);
    }
}