C++(g++ 7.5.0) 解法, 执行用时: 1396ms, 内存消耗: 512968K, 提交时间: 2022-11-04 14:22:09

#include <iostream>
using namespace std;
const int N = 1e8+1;
bool sushu[N];
int sum[N],prime[6000000],cnt;
void getPrime() {
	for (int i = 2; i < N; ++i) {
		if (!sushu[i]) {
			prime[++cnt] = i;
		}
		sum[i] = cnt;
		for (int j = 1; prime[j] <= N / i; ++j) {
			sushu[prime[j] * i] = 1;
			if (!(i%prime[j]))break;
		}
	}
}
int main() {
	getPrime();
	int t; cin >> t;
	while (t--) {
		int n, m; cin >> n >> m;
		cout << sum[m] - sum[n - 1] << endl;
		
	}
}

C++ 解法, 执行用时: 1522ms, 内存消耗: 512992K, 提交时间: 2022-01-16 11:11:25

#include<bits/stdc++.h>
using namespace std;
int pr[5761459];
bool npr[100000005];
int q[100000005];
int t;
int n,m;
int sum;
int main(){
for(int i=2;i<=100000000;i++){
	q[i]=q[i-1];
	if(!npr[i]){
		pr[++sum]=i;
		q[i]++;
	}
	for(int j=1;j<=sum&&i*pr[j]<=100000000;j++){
		npr[i*pr[j]]=1;
		if(i%pr[j]==0)break;
	}
}

cin>>t;
while(t--){
	scanf("%d %d",&n,&m);
	printf("%d\n",q[m]-q[n-1]);
    }
	return 0;
}