[POJ2689]Prime Distance

计算区间内的素数,区间的起始点和终止点可能很大(231),但是区间长度很小(106)。这题是筛素数的经典应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 65536;
bool com[MAXN], isp[1000001];
long long a, b, prime[MAXN];
int primes;
void GetPrimes()
{
  static bool com[MAXN];
  for (int i = 2; i < MAXN; ++i)
  {
    if (!com[i]) prime[primes++] = i;
    for (int j = 0; j < primes && i*prime[j] < MAXN; ++j)
    {
      com[i*prime[j]] = true;
      if (i % prime[j] == 0) break;
    }
  }
}
void GetPrimes(const int L, const int R)
{
  memset(isp, 1, sizeof(*isp)*(R-L+1));
  for (int i = 0; i < primes; ++i)
    for (int j = (L-1)/prime[i]+1, end = R/prime[i]; j <= end; ++j)
      isp[prime[i]*j-L] = false;
  for (int i = 0; i < primes && prime[i] <= R; ++i)
    if (prime[i] >= L)
      isp[prime[i]-L] = true;
  if (L == 1)
    isp[0] = false;
}
int main()
{
  GetPrimes();
  while (scanf("%I64d%I64d", &a, &b) != EOF)
  {
    GetPrimes(a, b);
    std::pair<long long, long long> smin, smax;
    long long min = 0x7FFFFFFF, max = 0, last = 0x7FFFFFFF;
    for (long long i = a; i <= b; ++i)
      if (isp[i-a])
      {
        if (last == 0x7FFFFFFF)
          { last = i; continue; }
        if (i-last < min)
        {
          min = i-last;
          smin = std::make_pair(last, i);
        }
        if (i-last > max)
        {
          max = i-last;
          smax = std::make_pair(last, i);
        }
        last = i;
      }
    if (max == 0)
      printf("There are no adjacent primes.\n");
    else
      printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n", smin.first, smin.second, smax.first, smax.second);
  }
}

Comments