20141021633-hd-メラニン数

美素数
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 23   Accepted Submission(s) : 4
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
明ちゃんは対数の研究が好きで、数といえば、頭の中に多くの問題が現れて、今日、明ちゃんは素数に対する認識を試験したいと思っています.問題は、1つの10進数が素数であり、その各数字と素数であれば、29のように「美素数」と呼ばれ、それ自体が素数であり、2+9=11も素数であるため、美素数である.区間を指定して、この区間に何個の美素数があるか計算できますか?
Input
1行目には、T組のデータが合計であることを示す正の整数Tが入力される(T<=10000).次にT行を合計し、各行に2つの整数L、R(1<=L<=R<=1000000)を入力し、区間の左値と右値を表す.
Output
各セットのデータについて、Case数を先に出力し、次に区間内の美素数の個数(端点値L,Rを含む)を出力する.各グループのデータは1行を占め、具体的な出力フォーマットはサンプルを参照してください.
Sample Input

3
1 100
2 2
3 19

Sample Output

Case #1: 14
Case #2: 1
Case #3: 4

           ，    。        。              ，               ，                   。

                     ，  num[m]-num[n-1],    num[n]        ，  num[n]   

#include<stdio.h>
#include<string.h>
int a[1100000],b[1100000],num[1100000];//         
int main()
{
	int t;
	int m,n;
	int i,j,k,l=1;
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(num,0,sizeof(num));
	a[0]=a[1]=1;
	for(i=0;i<1005000;i++)
	{
		if(a[i])
		    continue;
		for(j=i+i;j<1005000;j+=i)
		    a[j]=1;
	}//          
	for(i=0;i<1005000;i++)
	{
		if(a[i]==0)
		{
		    j=i;
		    k=0;
		    while(j)
		    {
			    k+=j%10;
			    j/=10;
		    }
		    if(a[k]==0)
		        b[i]=1;
		}
	} //         
	for(i=1;i<=1000000;i++)
	    if(b[i]==1&&a[i]==0)
	        num[i]=num[i-1]+1;
	    else
	        num[i]=num[i-1];//    ，num                  
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		printf("Case #%d: ",l);
		l++;
		printf("%d
",num[m]-num[n-1]);//   -num[n-1] 
	}
	return 0;
}