HDU 4548(筛法求素数)

http://acm.hdu.edu.cn/showproblem.php?pid=4548

筛法的话有模板，但是这题因为数据量有10000*1000000，所以如果在查找过程中没有比较优的算法的话，便会造成超时。

我自己起先也是超时，后来看了别人的写法，自己学着写了一个，是另外申请一个数组来存储所有的美素数的，数量大概有3w+。数组开少了会爆掉。然后在查找时只有找这个数组就可以了，时间在10000*30000，一般不会超时，ac时间453ms

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MAX 1000010
 4 int pri[MAX],ans[MAX];
 5 int len=0;
 6 int prime()
 7 {
 8     int i,j,sum,x,t;
 9     for(t=0;t<MAX;t++)pri[t]=1,ans[i]=0;
10     pri[0]=pri[1]=0;
11     for(i=2;i<=MAX;i++)
12     {
13         if(pri[i])
14         {
15             for(j=i*2;j<=MAX;j+=i)
16             pri[j]=0;
17             x=i;
18             sum=0;
19             while(x)
20             {
21                sum+=(x%10);
22                x/=10;
23             }
24             if(pri[sum])//判断是美素数
25             ans[len++]=i;
26         }
27     }
28 }
29 int main()
30 {
31     int t,l,r,sum,ca=1,i;
32     prime();
33     scanf("%d",&t);
34     while(t--)
35     {
36          scanf("%d%d",&l,&r);
37          sum=0;
38          for(i=0;i<=len;i++)//只要在这个数组里一个一个找属于区间里的数即可
39          if(ans[i]>=l&&ans[i]<=r)sum++;
40          printf("Case #%d: %d
",ca++,sum);
41     }
42     return 0;
43 }

View Code

时间有点多。。。然后自己又有了一种新的想法，另开一个数组，每个元素里存储包括这个元素在内的之前所有美素数的个数。。写完时间是31ms

#include<stdio.h>
#include<string.h>
#define MAX 1000010
int pri[MAX],ans[MAX],hash[MAX];
int prime()
{
    int i,j,sum,x,t;
    for(t=0;t<MAX;t++)pri[t]=1,ans[t]=0,hash[t]=0;
    pri[0]=pri[1]=0;
    for(i=2;i<=MAX;i++)
    {
            sum=0;
        if(pri[i])
        {
            for(j=i*2;j<=MAX;j+=i)
            pri[j]=0;
            x=i;
            while(x)
            {
               sum+=(x%10);
               x/=10;
            }
            hash[i]=pri[sum];
        }
            ans[i]=ans[i-1]+pri[sum];
    }
}
int main()
{
    int t,l,r,sum,ca=1;
    prime();
    scanf("%d",&t);
    while(t--)
    {
         scanf("%d%d",&l,&r);
         sum=0;
         
         if(hash[l])sum=ans[r]-ans[l]+1;
         else sum=ans[r]-ans[l];
         printf("Case #%d: %d
",ca++,sum);
    }
    return 0;
}

View Code