本题就是能够直接打表的，推断能否够打表也须要技巧的：

1 推断最大的数值为1000000。百万下面的数打表都是能够的

2 能够线性预处理好。使用素数筛子法是能够接近线性预处理的。

故此能够打表了。

须要熟悉的基本知识点：

1 素数筛子法 - 一两分钟之内写出代码

2 一般素数推断法，由于位数相加之后的数值很小，故此一般素数推断就能够了，假设写个primality test 算法会大材小用了。

3 然后是带点动态规划法的思想把前面的美素数叠加起来，方便查找。

算是基础题目了，也是有人说的水题，我还是喜欢叫基础题吧。

难在于推断好，并运用好这些基础知识。简单优雅地解决，写出代码。

#include <stdio.h>

#include <string.h>

const int MAX_N = 1000001;

bool isPrime(int n)

{

	if (n == 2) return true;

	for (int r = 2; r * r <= n; r++)

	{

		if (n % r == 0) return false;

	}

	return true;

}

bool isMeiPrime(int n)

{

	int d = 0;

	while (n)

	{

		d += n % 10;

		n /= 10;

	}

	return isPrime(d);

}

int primeNums[MAX_N];

bool primes[MAX_N];

void seive()

{

	memset(primes, 0, MAX_N * sizeof(bool));

	for (int i = 2; i < MAX_N; i++)

	{

		if (!primes[i])

		{

			for (int j = i << 1; j < MAX_N; j += i)

			{

				primes[j] = true;

			}

		}

	}

	primeNums[0] = 0, primeNums[1] = 0;

	for (int i = 2; i < MAX_N; i++)

	{

		if (!primes[i] && isMeiPrime(i)) primeNums[i] = primeNums[i-1] + 1;

		else primeNums[i] = primeNums[i-1];

	}

}

int main()

{

	seive();

	int T, a, b;

	scanf("%d", &T);

	for (int t = 1; t <= T; t++)

	{

		scanf("%d %d", &a, &b);

		printf("Case #%d: %d\n", t, primeNums[b] - primeNums[a-1]);

	}

	return 0;

}