??

素?cái)?shù)距離問(wèn)題

時(shí)間限制：3000 ms? |? 內(nèi)存限制：65535 KB

難度：2

描述 現(xiàn)在給出你一些數(shù)，要求你寫出一個(gè)程序，輸出這些整數(shù)相鄰最近的素?cái)?shù)，并輸出其相距長(zhǎng)度。如果左右有等距離長(zhǎng)度素?cái)?shù)，則輸出左側(cè)的值及相應(yīng)距離。
?如果輸入的整數(shù)本身就是素?cái)?shù)，則輸出該素?cái)?shù)本身，距離輸出0
輸入第一行給出測(cè)試數(shù)據(jù)組數(shù)N(0<N<=10000)
接下來(lái)的N行每行有一個(gè)整數(shù)M(0<M<1000000)，輸出每行輸出兩個(gè)整數(shù) A B.
其中A表示離相應(yīng)測(cè)試數(shù)據(jù)最近的素?cái)?shù)，B表示其間的距離。樣例輸入3
6
8
10
樣例輸出
5 1
7 1
11 1

原始鏈接: http://acm.nyist.net/JudgeOnline/problem.php?pid=24

解題思路：
素?cái)?shù)表是需要多次使用的，先計(jì)算出來(lái)，節(jié)約時(shí)間
然后每輸入一個(gè)m，就依次檢查m,m-1,m+1,m-2,m+2,。。。。這樣的序列
x=x<0?-x:-(x+1)這一句就是用來(lái)計(jì)算這個(gè)序列的
一旦發(fā)現(xiàn)是素?cái)?shù)，那就是我們需要的結(jié)果

最終代碼如下。
速度上應(yīng)該還有優(yōu)化的空間，比如用二分法查找小于m的最大素?cái)?shù)，素?cái)?shù)表中
下一項(xiàng)就是大于等于m的最小素?cái)?shù)，比較這兩個(gè)值和m的差，其中比較小的就是
我們需要的結(jié)果。

#include#includeint?main(void)	{
	int?i,n,j,ss[1000]={2},ss2[1000]={4},m,x,ps=1;
	scanf("%dn",&n);
	for(i=3;i<1012;i=i+2)	{
		for(j=0;ss2[j]i)	{
			ss[ps]=i;
			ss2[ps++]=i*i;
		};
	};
	while(n--)	{
		scanf("%d",&m);
		if(m==1)	{
			puts("2?1");
			continue;
		};
		for(x=0;;)	{
			i=m+x;
			for(j=0;ss2[j]i)	{
				printf("%d?%dn",i,x>0?i-m:m-i);
				break;
			};
			x=x<0?-x:-(x+1);
		};
	};
	return?0;
}