题解 | #经此一役小红所向无敌#

H题漂亮数

小红定义一个数满足以下条件为“漂亮数”：

1. 该数不是素数。
2. 该数可以分解为2个素数的乘积
   求区间L-R的漂亮数个数

这题考察对素数筛的简单理解。
欧拉筛(线筛)，每次都会把一定范围内素数倍数的数筛为合数，并且每个数只会筛到一次（primes[j]*i），那么筛掉的这个数已经满足了不是素数，其中一个数是素数，我们只要判断乘的那个倍数i是否为素数即可，前缀和预处理1e8，O(1)查询即可。

#include<bits/stdc++.h>
const int N = 1e8 + 5;
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
//#define int long long
bool vis[N];
int ans[N];
bool p[N];int primes[N];int cnt;
void shai(int n)//欧拉筛
{
    memset(p,true,sizeof(p));
    p[0]=p[1]=false;
    for(int i=2;i<=n;++i)
    {
        if(p[i])primes[++cnt]=i;
        for (int j=1;j<=cnt&&primes[j]*i<=n;++j)
        {
            p[primes[j]*i] = 0;
            if(p[i])vis[primes[j]*i]=1;//核心代码一行
            if (i%primes[j]==0) break;
        }
    }
    for(int i=1;i<=n;i++)
        ans[i]+=ans[i-1]+(vis[i]==1);
}
int main()
{
    shai(1e8);
    int t;
    cin>>t;
    while(t--)
    {
        int l,r;
        cin>>l>>r;
        cout<<ans[r]-ans[l-1]<<endl;
    }
    return 0;
}