C 解法, 执行用时: 1306ms, 内存消耗: 806412K, 提交时间: 2022-08-13 17:49:24

#include<stdio.h>
const int N=1e8+10;
int pri[N],pre[N],cnt;
int st[N];
void init()
{
	for(int i=2; i<=1e8; i++)
	{
		if(st[i]==0)pri[cnt++]=i;
		pre[i]=pre[i-1];
		if(st[i]==1)
		{
			pre[i]++;
		}
		for(int j=0; pri[j]<=1e8/i; j++)
		{
			st[i*pri[j]]=st[i]+1;
			if(i%pri[j]==0)break;
		}
	}
}
int main()
{
	init();
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",pre[r]-pre[l-1]);
	}
}

C++ 解法, 执行用时: 2572ms, 内存消耗: 806556K, 提交时间: 2022-07-20 18:49:45

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e8+10;
int a[N],v[N],c,sum[N],l,r;

void sushu(){
	for(int i=2;i<=1e8;i++){
		if(v[i]==0) a[++c]=i;
		sum[i]=sum[i-1];
		if(v[i]==1) sum[i]++; 
		for(int j=1;i*a[j]<=1e8;j++){
			v[i*a[j]]=v[i]+1;
			if(i%a[j]==0) break;
		}
	}
	
}
int main(){
	int t;
	cin>>t; 
	sushu();
	while(t--){
		cin>>l>>r;
	cout<<sum[r]-sum[l-1]<<endl; 
	}
	return 0;
}