题目描述：

　　　　　　在小X的认知里，质数是除了本身和1以外，没有其他因数的数。

　　　　　　但由于小 X对质数的热爱超乎寻常，所以小X同样喜欢那些虽然不是质数，但却是由两个质数相乘得来的数。

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

输入格式：

　　　　　　　　第一行输入个正整数 Q，表示询问的组数。
　　　　　接下来 Q行，包含两个正整数 L和 R，保证 L≤R（1<=L<=R<=10000000）。

输出格式：

　　　　　　　　输出 Q行，每一个整数，表示该区间范围内小 X喜欢的数的个数。

样例输入

　　　　1 6

样例输出

解题思路：

　　　　　　这道题目的数据非常的大，到了1千万！所以，用普通的筛表法+后来要查询时用到的q*二个二分查找肯定是超时的。所以我们要用厉害一点的筛——线性筛。

　　线性筛其实是个模板。i从2循环到1千万，如果当前的在数组f中i这个位置标记为0的话，则i为素数，将数组f中i这个位置赋为i，并将i放入数组p中。判断如果当前f[i]==i||f[i/f[i]]==i/f[i],则用前缀和sum[i]=sum[i-1]+1,否则sum[i]=sum[i-1]。再来一重循环j，从1到j<=p数组中数的个数&&p[j]<=f[i]，当i*p[j]在1千万以内时，则f[i*p[j]]=p[j]。

　　　用线性筛，筛的时候用O（n），而到查询时则用q*O（1），所以总时间复杂度为O（n+q），这样就不用怕超时了。

代码：（请不要直接拷贝哦）

1 #include <cstdio>

2 #define maxn 10000005

3 int f[maxn],p[4000000],sum[maxn],t;

4 using namespace std;

 5 int main()
 6 {
 7 　　int q;
 8 　　scanf("%d",&q);
 9 　　for (int i=2;i<=maxn;i++)//线性筛
10 　　{
11 　　　　if (!f[i])
12 　　　　{
13 　　　　　　f[i]=i;
14 　　　　　　p[++t]=i;
15 　　　　}
16 　　　　if ((f[i]==i)||(f[i/f[i]]==i/f[i])) sum[i]=1;
17 　　　　　　sum[i]+=sum[i-1];
18 　　　　for (int j=1;j<=t&&p[j]<=f[i];j++)
19 　　　　{
20 　　　　　　if (i*p[j]>maxn) break;
21 　　　　　　f[i*p[j]]=p[j];
22 　　　　}
23 　　}
24 　　for (int i=1;i<=q;i++)
25 　　{
26 　　　　　int x,y;
27 　　　　　scanf("%d%d",&x,&y);
28 　　　　　printf("%d\n",sum[y]-sum[x-1]);
29 　　}
       return 0；
30 }

秒客网

小X的质数