C++ 解法, 执行用时: 1566ms, 内存消耗: 63108K, 提交时间: 2021-12-25 22:48:12

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+100;
int cnt[N],num[N],ans[N];
struct node{
	int n,k,pos;
}w[N];

inline void pre()
{
	for(int i=2;i<=3000010;i++)
	{
		for(int j=i;j<=3000010;j+=i)
			if(!num[j])
				num[j]=i;
	}
}

inline int cmp(node s1,node s2)
{
	return s1.n<s2.n;
}

inline void update(int x)
{
	for(int i=x;i<=3000010;i+=(i&(-i)))
		cnt[i]+=1;
}

inline int query(int x)
{
	int sum=0;
	for(int i=x;i;i-=(i&(-i)))
		sum+=cnt[i];
	return sum;
}

int main()
{
	pre();
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
		scanf("%d%d",&w[i].n,&w[i].k),w[i].pos=i;
	sort(w+1,w+1+q,cmp);
	
	int x=2;
	for(int i=1;i<=q;i++)
	{
		while(x<=w[i].n)
		{
			update(num[x]);
			x++;
		}
		ans[w[i].pos]=w[i].n-query(w[i].k-1)-1;
	}
	
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
	return 0;
}