340      阿裏雲  技術社區[雲棲]

【端午小練】HDU4548-美素數

美素數
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2132    Accepted Submission(s): 734

Problem 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
 

Source
2013金山西山居創意遊戲程序挑戰賽——初賽（2）

題不難，就是初始化不容易，要求用最省時的辦法來獲得美素數的數組，再次懂得，用打表法需謹慎
AC代碼：

#include<stdio.h>
#include<string.h>
#include<math.h>
int flag[1000010],num[1000010],beau[1000010];
void isfull(int n)
{
    int x,m,k=0,sum=0;
    m=n;
    while(m)
    {
       x=m%10;
       sum+=x;
       m/=10;
    }   
    if(flag[sum]==0)
    num[n]=1;
}
int main()
{
   int i,j,T,n,m,sum,v=1;
   memset(flag,0,sizeof(flag));
   memset(num,0,sizeof(num));
   memset(beau,0,sizeof(beau));
   flag[1]=-1;
   for(i=2;i<=1000000;i++)//打素數表 
   {
     if(flag[i]==0)
     {
        for(j=2*i;j<=1000000;j+=i)
        flag[j]=-1;
     }
   }
   for(i=2;i<=1000000;i++)//判斷是否是美素數 
   {
      if(flag[i]==0)
      {
         isfull(i);
      }
   }
   for(i=2;i<=1000000;i++)//beau[i]的意思是，從1至i的美素數的個數 
   {
      if(num[i]==1)
      beau[i]=beau[i-1]+1;
      else
      beau[i]=beau[i-1];
   }
   scanf("%d",&T);
   while(T--)
   {
      sum=0;
      scanf("%d %d",&n,&m);
      printf("Case #%d: %d\n",v++,beau[m]-beau[n-1]); //直接獲取區間內的美素數個數 
   }
   return 0;
}

最後更新：2017-04-03 08:26:19

  上一篇： 扯談web安全之JSON

  下一篇： 動態規劃-hdoj-4832-百度之星2014初賽第二場