329
素数最短距离算法
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define MAX_LENGTH 50000001
bool prime[MAX_LENGTH];
void CreatePrimeTable()
{
int i, j;
memset(prime, true, sizeof(prime)); // 初始化全为1
prime[0] = prime[1] = false; // 0和1不是素数
for (i = 2; i * i < MAX_LENGTH; i++)
{
if (prime[i]) // 如果是素数
{
// 如果i是素数，那么能整除i的肯定不是素数
for (j = i * 2; j < MAX_LENGTH; j += i)
{
prime[j] = false;
}
}
}
}
int main()
{
int number = 0;
long prevDist = 0, // 当前素数与前一个素数的距离
nextDist = 0; // 当前素数与后一个素数的距离
int i = 0, j = 0;
CreatePrimeTable();
while (scanf("%d", &number) != EOF)
{
prevDist = 0;
nextDist = 0;
if (prime[number]) // 如果是素数
{
printf("%d ", number);
for (i = number - 1; i >= 2; i--)
{
if (prime[i] != 0)
{
prevDist = number - i;
break;
}
}
for (i = number + 1; i < MAX_LENGTH; i++)
{
if (prime[i] != 0)
{
nextDist = i - number;
break;
}
}
printf("%d\n", prevDist < nextDist ? prevDist : nextDist);
}
else
{
printf("%d不是素数\n", number);
}
}
return 0;
}
最后更新：2017-04-03 18:52:05