登录—专业IT笔试面试备考平台_牛客网
 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'const int N=1e8+5;
int primes[N],cnt;
bool st[N];
int ans[N];
/*
//多余
bool divide(int n)
{int cnt=0;for(int i=2;i<=n/i;i++){if(n%i==0){while(n%i==0){cnt++;if(cnt>2)return false;n/=i;}}}if(n)cnt++;if(cnt!=2)return false;else return true;
}
*/
void get_primes(int n)
{for(int i=2;i<=n;i++){if(!st[i]){primes[cnt++]=i;}for(int j=0;primes[j]<=n/i;j++){st[primes[j]*i]=true;//if(divide(primes[j]*i))ans[primes[j]*i]=1;//这里不需要一个一个判断，如果st[i]==0代表i就是原始素数//那么i*primes[j]就是两素数之积if(!st[i])ans[primes[j]*i]=1;if(i%primes[j]==0)break;}}
}int main()
{get_primes(N-1);for(int i=1;i<=N-1;i++)ans[i]+=ans[i-1];//因为需要10^5次查找而且查找范围为10^8,所以为省时可以一次性查完所有int t;cin>>t;while(t--){int l,r;cin>>l>>r;cout<<ans[r]-ans[l-1]<<endl;}
}