素数最短距离算法

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