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

  上一篇： Android SurfaceView運行機製詳解—剖析Back與Home按鍵及切入後台等異常處理！

  下一篇： Android 休眠狀態對Camera預覽的影響