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);
}
}
|
