??

素數距離問題

時間限制：3000 ms? |? 內存限制：65535 KB

難度：2

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

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

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

最終代碼如下。
速度上應該還有優(yōu)化的空間，比如用二分法查找小于m的最大素數，素數表中
下一項就是大于等于m的最小素數，比較這兩個值和m的差，其中比較小的就是
我們需要的結果。

#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;
}