美素数

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88159#problem/H

题意：

     一个十进制数，如果是素数，而且它的各位数字和也是素数，则称之为“美素数”。计算在所输入的区间中有多少个美素数。

     案例：

     input

     3

     1 100

     2 2

     3 19

     output

     Case #1: 14

     Case #2: 1

     Case #3: 4

思路分析：

     最多可能有1000000个数，又最多有10000种案例，最坏的情况会是循环10000000000次，数过大，会超时，应该要进行打表。

     把所有数都标记为1，先找出所有不是素数的数标记为0（去掉），再找出满足条件的素数，计录从1开始到i的所有满足条件的数的个数b[i]。

     在案例输入后，只要输出b[R]-b[L-1]即可。

源代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAX 1000000
using namespace std;
int a[MAX+5],b[MAX+5];
int main()
{
    int T,L,R,i,j,t=0;
    for(i=2;i<=MAX;i++)
        a[i]=1;
    b[0]=a[0]=a[1]=0;
    for(i=2;i<=1000;i++)
        if(a[i])
            for(j=i*i;j<=MAX;j+=i)
                a[j]=0;
    for(i=1;i<=MAX;i++)
    {
        b[i]=b[i-1]+a[i];
        if(a[i])
        {
            int k=i,sum=0;
            while(k)
            {    
                sum+=k%10;
                k=k/10;    
            }
            if(!a[sum])
                b[i]=b[i]-1;
        }
    }
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&L,&R);
        printf("Case #%d: %d
",++t,b[R]-b[L-1]);
    }
    return 0;
}