prime_distance.cpp

Prime Distance算法的源码 Prime Distance算法的源码 Prime Distance算法的源码

#include <stdio.h>
#include <string.h>
#include <math.h>
long long ns[1000002], ps[4792];
int main()
{
	long long i, j, k, min, max, minl, minu, maxl, maxu, temp, l ,u;
	memset(ns, 0, sizeof(ns));
	ps[0] = 2;
	k = 1;
	for (i = 3; i < 46340; i += 2)
	{
		if (ns[i] == 0)
		{
			ps[k++] = i;
			for (j = i + i; j < 46340; j += i)
			{
				ns[j] = 1;
			}
		}
	}
	while (scanf("%lld %lld", &l, &u) != EOF)
	{
		memset(ns, 0, sizeof(ns));
		k = 0;
		if (l <= 2)
		{
			l = 3;
			ns[k++] = 2;
		}
		else
		{
			if (!(l & 1))
			{
				l++;
			}
		}
		temp = (long long)sqrt(u);
		for (i = 1; ps[i] <= temp && i <= 4791; i++)
		{
			for (j = l / ps[i] * ps[i]; j < l; )
			{
				j += ps[i];
			}
			if (j == ps[i])
			{
				j += ps[i];
			}
			for ( ; j <= u; j += ps[i])
			{
				ns[j - l + 1] = 1;
			}
		}
		if (ns[0] == 2)
		{
			i = 1;
		}
		else
		{
			i = 0;
		}
		for (j = u - l + 1, i = 1; i <= j; i += 2)
		{
			if (ns[i] == 0)
			{
				ns[k++] = i + l - 1;
			}
		}
		if (k <= 1)
		{
			printf("There are no adjacent primes.\n");
		}
		else
		{
			maxl = minl = ns[0];
			maxu = minu = ns[1];
			for (max = min = ns[1] - ns[0], i = 2; i < k; i++)
			{
				if (ns[i] - ns[i - 1] > max)
				{
					max = ns[i] - ns[i - 1];
					maxl = ns[i - 1];
					maxu = ns[i];
				}
				else
				{
					if (ns[i] - ns[i - 1] < min)
					{
						min = ns[i] - ns[i - 1];
						minl = ns[i - 1];
						minu = ns[i];
					}
				}
			}
			printf("%lld,%lld are closest, %lld,%lld are most distant.\n", minl, minu, maxl, maxu);
		}
	}
	return 0;
}