C++14(g++5.4) 解法, 执行用时: 671ms, 内存消耗: 79352K, 提交时间: 2020-06-14 14:00:42

#include<bits/stdc++.h>
using namespace std;
int f[10000005];
int g[10000005];
void s(int a){
	f[1]=0;
	g[1]=1;
	for(int i=2;i<=a;i++){
		if(g[i]==0){
		f[i]=f[i-1]+1;
		for(int j=2*i;j<=a;j+=i){
			g[j]=1;
		} 
	}
	else
	f[i]=f[i-1];
}
}
int main(){
	int a,x,y;
	cin>>a;
	s(10000000);
	for(int i=1;i<=a;i++){
	cin>>x>>y;
	cout<<f[y]-f[x-1]<<endl;
}
}

C++11(clang++ 3.9) 解法, 执行用时: 525ms, 内存消耗: 157672K, 提交时间: 2020-06-15 10:38:58

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[10000005],v[10000005];
int main(){ 
	ll i,j,t,b,c,sum=0;
	for(i=2;i<=10000000;i++){
		if(v[i]==0){
			for(j=2*i;j<=10000000;j+=i){
				v[j]=1;
			}
			sum++;
		}
		a[i]=sum;
	}
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&b,&c);
		printf("%lld\n",a[c]-a[b-1]);
	}
}