http://poj.org/problem?id=2689

题意：给出一个大区间[L,U],分别求出该区间内连续的相差最小和相差最大的素数对。

由于L<U<=2147483647，直接筛素数是不行的，数组就开不了。可是能够依据素数筛的原理。我们先筛出sqrt(2147483647)以内的素数，然后拿这些素数去筛[L,U]之间的素数，即两次素数筛。可是L,U还是非常大，但U-L<=1000000,所以进行区间平移，将[L,U]平移为[0,U-L]，就能用数组放得下。

#include <stdio.h>

#include <iostream>

#include <map>

#include <set>

#include <stack>

#include <vector>

#include <math.h>

#include <string.h>

#include <queue>

#include <string>

#include <stdlib.h>

#include <algorithm>

#define LL long long

#define _LL __int64

#define eps 1e-12

#define PI acos(-1.0)

using namespace std;

const int maxn = 47000;

int prime[maxn];

bool flag[maxn];

bool a[1000010];

LL L,U;

void get_prime()

{

	memset(flag,true,sizeof(flag));

	prime[0] = 0;

	flag[0] = flag[1] = false;

	for(int i = 2; i < maxn; i++)

	{

		if(flag[i])

			prime[++prime[0]] = i;

		for(int j = 1; j <= prime[0]&&prime[j]*i < maxn; j++)

		{

			flag[prime[j]*i] = false;

			if(i%prime[j] == 0)

				break;

		}

	}

}

//用已筛选的素数去筛[L,U]之间的素数，区间平移为[0,U-L];

void solve(LL L, LL u)

{

	memset(a,true,sizeof(a));

	if(L == 1)//特殊推断L为1的时候，映射为0，但1不是素数，所以a[0]为false。

		a[0] = false;

	for(int i = 1; i <= prime[0]; i++)

	{

		if(prime[i]*prime[i] > U)

			break;

		int l = L/prime[i];

		if(L%prime[i]!=0)

			l++;

		if(l == 1) l = 2; // l=1时，L为素数，不能把L本身筛掉

		int u = U/prime[i];

		for(int j = l; j <= u; j++)

		{

			LL t = (long long)j*prime[i];

			a[t-L] = false;

		}

	}

}

int main()

{

	get_prime();

	while(~scanf("%lld %lld",&L,&U))

	{

		solve(L,U);

		int Min = 1000010,Max = -1;

		int ans[4];

		int x,y;

		x = y = -1;

		for(int i = 0; i <= U-L; i++)

		{

			if(a[i] == true)

			{

				x = y;

				y = i;

				if(x == -1)

					continue;

				int t = y-x;

				if(t < Min)

				{

					ans[0] = x;

					ans[1] = y;

					Min = t;

				}

				if(t > Max)

				{

					ans[2] = x;

					ans[3] = y;

					Max = t;

				}

			}

		}

		if(x != -1 && y != -1)

		{

			printf("%lld,%lld are closest, %lld,%lld are most distant.\n",ans[0]+L,ans[1]+L,ans[2]+L,ans[3]+L);

		}

		else

			printf("There are no adjacent primes.\n");

	}

	return 0;

}