POJ2689 Prime Distance 质数筛选

题目大意

求区间[L, R]中距离最大和最小的两对相邻质数。R<2^31, R-L<1e6。

总体思路

本题数据很大。求sqrt(R)的所有质数，用这些质数乘以j, j+1, j+2...k（j和k使得积属于[L,R]）筛选出[L,R]中的合数，然后在[L,R]的质数中得到所求。

筛法求质数

为在O(n)的时间复杂度中求得质数，我们要使筛选时每个可能为质数的数只访问一次。我们用v[i]表示i的最小质因数。每次循环到i时，假设v[i]和小于i的质数都已经在前面求出来了，若v[i]==0，则i是个质数。然后对于每个不大于v[i]的已知质数p，令v[i*p]=p。

不漏

证明：若i+1是个合数，则在处理i+1以前v[i+1]便已知。i+1必然可以化为若干个质数的积，记此质数的集合为P其中最小的质数为a，剩余质数的积为x。显然a<=x<=i。i之前循环到x时，a必然存在于已经求出的质数集合当中（因为a<=x），且a不大于v[x](因为a是P中最小的)。所以一定能由a*x得到i+1。

不重

证明：如果不要求p<=v[i]，则值p*i会重复计算若v[i]<=p<=i，则在i循环之前必会循环到p，那个时候就把v[i]*p给算了。

注意

本题中质数是从2开始的。
[L,R]质数中找所求时，避免1的出现，不能直接改循环初始条件。
筛选合数时，j至少为2，否则素数乘以1还是素数，我们却把它设成合数了。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdarg>

#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f, MAX_RANGE = 1000010, MAX_SQRT_N = 1 << 16;

#define LOOP(i, n) for(int i=0; i<n; i++)

#define LoopFrom(i, l, r) for(int i=l; i<r; i++)

#define LoopDown(i, n) for(int i=n-1; i>=0; i--)

int GetPrime(int *ans, int n)

{

	static int v[MAX_SQRT_N];

	memset(v, 0, sizeof(v));

	int ansCnt = 0;

	LoopFrom(i, 2, n + 1)

	{

		if (!v[i])

		{

			ans[ansCnt++] = i;

			v[i] = i;

		}

		for (int j = 0; j < ansCnt && ans[j] <= v[i] && ans[j] <= n/i; j++)

			v[ans[j] * i] = ans[j];

	}

	return ansCnt;

}

void Proceed(int l, int r)

{

	static int a[MAX_SQRT_N];

	static bool IsPrime[MAX_RANGE];

	memset(a, 0, sizeof(a));

	memset(IsPrime, false, sizeof(IsPrime));

	LOOP(i, r - l + 1)

		IsPrime[i] = true;

	int len = GetPrime(a, sqrt((double)r)+0.5);

	LOOP(i, len)

		LoopFrom(j, max((l / a[i])*a[i] < l ? l / a[i] + 1 : l / a[i], 2), r / a[i] + 1)

		    IsPrime[a[i] * j - l] = false;

	int minDist = INF, maxDist = 0, prev = -1;

	int c1=0, c2=INF, d1=0, d2=-INF;

	LoopFrom(i, 0, r - l + 1)

	{

		if (IsPrime[i] && i+l>1)

		{

			if (prev == -1)

			{

				prev = i;

				continue;

			}

			if (i - prev < c2 - c1)

			{

				c1 = prev;

				c2 = i;

			}

			if (i - prev > d2 - d1)

			{

				d1 = prev;

				d2 = i;

			}

			prev = i;

		}

	}

	if (c2 == INF)

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

	else

		printf("%d,%d are closest, %d,%d are most distant.\n", c1+l, c2+l, d1+l, d2+l);

}

int main()

{

	int l, r;

	while (~scanf("%d%d", &l, &r))

		Proceed(l, r);

	return 0;

}

筛法求质数2

void GetPrime(int *prime, int n)

{

	static bool NotPrime[MAX_N];

	memset(NotPrime,false,sizeof(NotPrime));

	int primeCnt=0;

	for(int i=2; i<=n; j++)

	{

		if(!NotPrime[i])

			prime[primeCnt++]=i;

		for(int j=0; j<primeCnt; j++)

		{

			if(i*prime[j]>N)

				break;

			NotPrime[i*prime[j]]=true;

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

				break;

		}

	}

}

不重

原则：对于一个数n都由它的最小质因数p和某一个数i相乘得到。

n的最小质因数只有1个，所以n只被访问了一次。

不漏

证明：对于n=p*i，p是n的最小质因数，当外层循环到当前i时，p一定会在循环j时被访问到。

因为n的质因数集合包含i的质因数集合，所以p小于等于i的最小质因数，而循环到当前i时，所有小于i的质数都求出来了，包含着i的最小质因数，故命题成立。

巴特西

POJ2689 Prime Distance 质数筛选

题目大意

总体思路

筛法求质数

不漏

不重

注意

筛法求质数2

不重

不漏

最新文章

热门文章