题目背景
小 X 是一位热爱数学的男孩子，在茫茫的数字中，他对质数更有一种独特的
情感。小 X 认为，质数是一切自然数起源的地方。
题目描述
在小 X 的认知里，质数是除了本身和 1 以外，没有其他因数的数字。
但由于小 X 对质数的热爱超乎寻常，所以小 X 同样喜欢那些虽然不是质数，
但却是由两个质数相乘得来的数。
于是，我们定义，一个数是小 X 喜欢的数，当且仅当其是一个质数，或是两
个质数的乘积。
而现在，小 X 想要知道，在 L 到 R 之间，有多少数是他喜欢的数呢？
输入输出格式
输入格式：
从文件 prime.in 中读取数据。
第一行输入一个正整数 Q，表示询问的组数。
接下来 Q 行，包含两个正整数 L 和 R，保证 L≤R。
输出格式：
输出 Q 行，每行一个整数，表示小 X 喜欢的数的个数。
输入输出样例
输入样例#1：
1
1 6
输出样例#1：
5
【样例 1 解释】
6 以内的质数有 2、3、5，而 4 = 2 * 2,6 = 2 * 3，因此，2,3,4,5,6 都是小 X 喜欢的数，而 1 不是.
L,R <= 10^7 Q <= 10^5
分析：这道题会线性筛就可以解决了.因为线性筛就是筛出素数并且剔除掉素数与另一个数i的乘积的，对于两个素数的乘积，我们只需要判断一下i是不是素数就好了
不过因为询问较多，所以要用前缀和处理.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
int q, l, r;
long long flag[], prime[], tot = , ans, vis[], vis2[], maxn;
long long sum[];
struct node
{
int l, r;
}e[]; void init(int r)
{
for (int i = ; i <= r; i++)
{
if (!flag[i])
{
prime[++tot] = i;
vis[i] = ;
}
for (int j = ; j <= tot; j++)
{
int t = i * prime[j];
if (t > r)
break;
flag[t] = ;
if (vis[i])
vis2[t] = ;
if (i % prime[j] == )
break;
}
}
} int main()
{
scanf("%d", &q);
for (int i = ; i <= q; i++)
{
scanf("%d%d", &e[i].l, &e[i].r);
if (e[i].r > maxn)
maxn = e[i].r;
}
init(maxn);
for (int i = ; i <= maxn; i++)
{
if (vis[i])
sum[i] = sum[i - ] + vis[i];
else
sum[i] = sum[i - ] + vis2[i];
}
for (int i = ; i <= q; i++)
printf("%lld\n", sum[e[i].r] - sum[e[i].l - ]); return ;
}