输入

第一行给出测试数据组数N(0<N<=10000)

接下来的N行每行有一个整数M(0<M<1000000)，

输出

每行输出两个整数 A B.

其中A表示离相应测试数据最近的素数，B表示其间的距离。

样例输入

36810

样例输出

5 17 111 1

来源

/**********************************   日期：2013-3-26*   作者：SJF0115*   题号: 题目24: 素数距离问题*   来源：http://acm.nyist.net/JudgeOnline/problem.php?pid=24*   结果：AC*   来源：南阳理工OJ*   总结：**********************************/#include
    
     #include
     
      #include
      
       #define MAX 1000010int prime[MAX];//素数表void Prime(){	memset(prime,0,sizeof(prime));	for(int i = 2;i < sqrt(MAX)+1;i++){		if(prime[i]){			continue;		}		else{			for(int j = i*i;j < MAX;j += i){				prime[j] = 1;			}		}	}}int main(){	int N,M,LIndex,RIndex;	//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);	Prime();	prime[1] = 1;	prime[0] = 1;	scanf("%d",&N);	//N组测试数据	while(N--){		scanf("%d",&M);		if(prime[M] == 0){			printf("%d 0\n",M);		}		else{			RIndex = M;			LIndex = M;			//寻找左边素数			while(prime[LIndex] == 1 && LIndex >= 0){				LIndex --;			}			//寻找右边素数			while(prime[RIndex] == 1){				RIndex ++;			}			//左边没有找到			if(LIndex < 0){				printf("%d %d\n",RIndex,RIndex-M);			}			//左右都有			else if(M - LIndex <= RIndex - M){				printf("%d %d\n",LIndex,M-LIndex);			}			else{				printf("%d %d\n",RIndex,RIndex-M);			}		}	}	return 0;}
      
     
    

注意：求素数表时MAX取值要大于1000003.因为距离999999最近的素数就是1000003