??

素數(shù)距離問題

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

難度：2

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

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

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

最終代碼如下。
速度上應(yīng)該還有優(yōu)化的空間，比如用二分法查找小于m的最大素數(shù)，素數(shù)表中
下一項就是大于等于m的最小素數(shù)，比較這兩個值和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;
}