漂亮数 (线性筛+前缀和)

登录—专业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;
	}
}