题面

考点
线性筛法+dp思维+处理区间的技巧
线性筛法的复杂度为o(n)
线筛
线筛的思想就是找到一个素数之后把它储存在素数数组里面，然后利用素数*当前的i得到很多合数。

const int MAX=1e9;
int isnotprime[MAX]={1,1},sushu[MAX],num;
void prime(){
	int i,j;
	for(i=2;i<=MAX;i++){
     if(!isnotprime[i])
	sushu[num++]=i;
     for(j=0;j<num&&i*sushu[j]<=MAX;j++){
	isnotprime[i*sushu[j]]=1;
	if(i%sushu[j]==0)//如果对这一步不理解的可以点一下上面的链接
		break;
     }
	}
}

所以线筛就是可以用o(1)的时间来查询某一个数是否是素数。
对于这一题，它让你求出某一个区间里面符合既是素数而且各位之和也为素数的数有多少个。
如果对区间处理不熟悉得话，可能会从left枚举到right的值，但是这个区间的范围过大就会运行超时。
这时我们就可以用区间处理的思想，可以尝试找到[1,left-1]与[1,right]中符合条件的个数，然后做差就可以得到最终结果。
而这个怎么更新[1,n]是一个dp思维，我们可以这样想[1,n]是由[1,n-1]得来的，所以[1,n]的值就主要由n是不是素数来决定。

void ispprime()
{
	int i;
	a[0] = 0;
	a[1] = 0;
	for( i = 2; i <MAX; i++)
	{
		a[i] = a[i-1];
		if(isprime[i] &&isprime[solve(i)])
		a[i]++;
	}
}

AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1000005//求MAX范围内的素数
int isprime[MAX],a[MAX],cnt,su[MAX];
void prime()
{
    cnt=1;
    for(int i=2;i<=MAX;i++)
	isprime[i]=1;//初始化认为所有数都为素数
    isprime[0]=isprime[1]=0;//0和1不是素数
    for(long long i=2;i<=MAX;i++)
    {
        if(isprime[i])
            su[cnt++]=i;//保存素数i
        for(long long j=1;j<cnt&&su[j]*i<MAX;j++)
        {
            isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数
            if(i%su[j]==0) break;
        }
    }
}
int solve(int a){
    int ans=0;
    while(a){
	ans=ans+a%10;
	a/=10;
    }
    return ans;
}
void ispprime()
{
	int i;
	a[0] = 0;
	a[1] = 0;
	for( i = 2; i <MAX; i++)
	{
		a[i] = a[i-1];
		if(isprime[i] &&isprime[solve(i)])
		a[i]++;
	}
}
int main()
{
   int t,left,right,time=1;
   cin>>t;
     prime();
     ispprime();//这个要放到外面不然会超时，主要是因为这时要测试多次
   while(t--){
	int num=0;
	cin>>left>>right;
	   num=a[right] - a[left-1];
	printf("Case #%d: %d\n",time,num);
	time++;
   }
    return 0;
}