261
素數最短距離問題
素數距離問題時間限製：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
//這裏效率上不高，我主要是練習使用篩法求素數！
代碼如下：
#include <iostream>
#include <cstring>//用到memset
//#include <ctime>
//#include <cstdio>
using namespace std;
#define MAX_SIZE 5000000//定義這麼大是為了保證與M最近的素數可能是超過100萬
bool isPrime[MAX_SIZE];
void CreatePrimeTable()
{
//clock_t start = clock();
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
int i, j;
for (i = 2; i * i <= MAX_SIZE; i++)
{
if (isPrime[i])
{
for (j = i * 2; j <= MAX_SIZE; j += i)
isPrime[j] = false;
}
}
//cout << "TIME:" << clock()-start << "ms" << endl;
}
int main()
{
CreatePrimeTable();
int m;
cin >> m;
for (int i = 1; i <= m; i++)
{
long s;
cin >> s;
if (isPrime[s])
cout << s << " " << 0 << endl;
else
{
long a, b, dis1, dis2;
for (a = s-1; a >= 2; a--)
{
if (isPrime[a])
{
dis1 = s - a;
break;
}
}
for (b = s+1; ; b++)
{
if (isPrime[b])
{
dis2 = b - s;
break;
}
}
if (dis1 <= dis2)
cout << a << " " << dis1 << endl;
else
cout << b << " " << dis2 << endl;
}
}
return 0;
}
最後更新：2017-04-02 15:14:53