题目大意

于是，我们定义，一个数是小X 喜欢的数，当且仅当其是一个质数，或是两个质数的乘积。

试求出在 \(L\) 到 \(R\) 之间，有多少个数是一个质数，或是两个质数的乘积呢？

解题思路

质数线性筛。

多求个两质数的乘积，再求个前缀和就行了。

AC CODE

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 10000001;

int n, cnt, pri[maxn], num[maxn], vis[maxn];

void kkk()
{
    for(int i = 2; i < maxn; ++i)
    {
        if(!vis[i]) 
		{
			pri[++cnt] = i;
			num[i] = 1;
		}
        num[i] += num[i - 1];
        for(int j = 1; j <= cnt; ++j)
        {
            if(pri[j] * i >= maxn) break;
            if(!vis[i]) num[i * pri[j]] = 1;
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}

signed main()
{
    kkk();
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%lld%lld", &a, &b);
        printf("%lld\n", num[b] - num[a - 1]);
    }
    return 0;
}