You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
49 lines
1.4 KiB
C++
49 lines
1.4 KiB
C++
#include <cmath>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
int prime_count;
|
|
int prime[5140];
|
|
bool f[1000010];
|
|
bool notprime[50010];
|
|
int main()
|
|
{
|
|
for (int i = 2; i < 50010; i++)
|
|
if (!notprime[i])
|
|
for (long long j = 1ll * i * i; j < 50010; j += i)
|
|
notprime[j] = true;
|
|
for (int i = 2; i < 50010; i++)
|
|
if (!notprime[i])
|
|
prime[prime_count++] = i;
|
|
int l, r;
|
|
while (~scanf("%d%d", &l, &r))
|
|
{
|
|
l = l == 1 ? 2 : l;
|
|
memset(f, 0, sizeof(f));
|
|
for (int i = 0, a, b; i < prime_count; i++)
|
|
{
|
|
a = (l - 1) / prime[i] + 1;
|
|
b = r / prime[i];
|
|
for (int j = a; j <= b; j++)
|
|
if (j > 1)
|
|
f[j * prime[i] - l] = true;
|
|
}
|
|
int mx = -1, mn = 0x3f3f3f3f, x1 = 0, x2 = 0, y1 = 0, y2 = 0;
|
|
for (int i = 0, p = -1; i <= r - l; i++)
|
|
if (!f[i])
|
|
{
|
|
if (~p)
|
|
{
|
|
if (mx < i - p)
|
|
mx = i - p, x1 = p + l, y1 = i + l;
|
|
if (mn > i - p)
|
|
mn = i - p, x2 = p + l, y2 = i + l;
|
|
}
|
|
p = i;
|
|
}
|
|
if (mx == -1)
|
|
puts("There are no adjacent primes.");
|
|
else
|
|
printf("%d,%d are closest, %d,%d are most distant.\n", x2, y2, x1, y1);
|
|
}
|
|
return 0;
|
|
} |