小X的质数

时间:2024-01-22 08:25:50

题目描述:

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

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

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

输入格式:

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

输出格式:

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

样例输入 

    1

    1 6

样例输出 

    5

解题思路:

      这道题目的数据非常的大,到了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 }

 

 

 

OVER!