HDU 4548 美素数

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int prime[1000005],b[1000005];
 5 int N=1000000;
　　　　//打素数表
 6 void set_prime()
 7 {
 8     prime[0]=1;      //这里是标记多余的一个数为1
 9     prime[1]=1;      //因为1不是素数所以要标记为1
10     for(int i=2; i<=sqrt(N); i++)
11     {
12         if(!prime[i])
13         {
14             for(int j=i*i; j<N; j+=i)   //这里表示i的倍数不是素数。（用j+j更加直观一些，用j*j更省时，但是为什么可以用j*j，我也一时没反应过来，毕竟是小白.. (⊙﹏⊙)b）
15                 prime[j]=1;
16         }
17     }
18 }
19 
　　　//打美素数的个数表..
20 void set_ansbiao()
21 {
22     int time=0,k;
23     for(int i=0; i<N; i++)
24     {
25         if(!prime[i])   //是素数
26         {
27             int sum=0;
28             k=i;
29             while(k)
30             {
31                 sum+=k%10;
32                 k=k/10;
33             }
34             if(!prime[sum])   //它的和是素数...
35                 time++;       // 个数加1
36         }
37         b[i]=time;         //个数用数组储存下来
38     }
39 }
40 
41 int main()
42 {
43     set_prime();
44     set_ansbiao();
45     int T,cas=0;
46     scanf("%d",&T);
47     while(T--)
48     {
49         int L,R;
50         scanf("%d%d",&L,&R);
51         cas++;
52         printf("Case #%d: %d\n",cas,b[R]-b[L-1]);    // 输出个数....
53     }
54     return 0;
55 }