//容易超時

?

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

?

?

#include <stdio.h>#include <math.h>int b[555555];bool sushu(int a){if(a==1)return false;int i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}bool wei(int b){int sum=0;if(!sushu(b))return 0;while(b){sum+=b%10;b/=10;}if(sushu(sum))return true;return false;}int main(){int t;int ti=1;int l,r,i,j,k;k=0;for(i=2;i<=1000001;i++){if(wei(i))b[k++]=i;}scanf("%d",&t);while(t--){int ans=0;scanf("%d%d",&l,&r);for(i=0;i<k;i++){if(b[i]>=l &&b[i]<=r)ans++;}printf("Case #%d: %d\n",ti++,ans);}return 0;}

?

轉載于:https://www.cnblogs.com/awsent/p/4267036.html

總結

以上是生活随笔為你收集整理的美素数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。