HDU 4548 美素數，hdu4548美素數

HDU 4548 美素數，hdu4548美素數

Description

　　小明對數的研究比較熱愛，一談到數，腦子裡就湧現出好多數的問題，今天，小明想考考你對素數的認識。  　　問題是這樣的：一個十進制數，如果是素數，而且它的各位數字和也是素數，則稱之為“美素數”，如29，本身是素數，而且2+9 = 11也是素數，所以它是美素數。  　　給定一個區間，你能計算出這個區間內有多少個美素數嗎？  

Input

第一行輸入一個正整數T，表示總共有T組數據(T <= 10000)。  接下來共T行，每行輸入兩個整數L，R(1<= L <= R <= 1000000)，表示區間的左值和右值。  

Output

對於每組數據，先輸出Case數，然後輸出區間內美素數的個數（包括端點值L,R）。  每組數據占一行，具體輸出格式參見樣例。  

Sample Input

3 1 100 2 2 3 19  

Sample Output

Case #1: 14 Case #2: 1 Case #3: 4     解題思路：為了不超時，就要打素數表了。這裡還要打一個美素數的個數表..        代碼如下：（詳情看注釋）    

 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 }