Prime Distance
链接：
题目大意：
给定两个正整数 \(l,r\)，求 \([l,r]\) 间 相邻 的两个差最大的质数和 相邻 的两个差最小的质数。如果区间内质数个数 \(\le 1\)，输出 There are no adjacent primes.。
思路：
水题，通过前 \(2^16\) 个质数排除 \([l,r]\) 之间的合数。
代码：
const int N = 1e6 + 10;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int pri[N], tot;
bool vis[N];
void Prework()
{
for (int i = 2; i <= N - 10; i++)
{
if (!vis[i]) pri[++tot] = i;
for (int j = 1; j <= tot && i * pri[j] <= N - 10; j++)
{
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
int main()
{
Prework();
for (ll l, r; ~scanf("%lld%lld", &l, &r); )
{
ll a, b, dif1 = 1ll << 60, c, d, dif2 = 0;
memset (vis, 0, sizeof vis);
if(l == 1) vis[0] = 1;
for (int i = 1; i <= tot; i++)
for (ll j = l / pri[i]; j * pri[i] <= r; j++)
if(j > 1 && j * pri[i] >= l)vis[j * pri[i] - l] = 1;
ll lst = 0;
for (ll i = l; i <= r; i++)
{
if (vis[i - l]) continue;
if (!lst) {lst = i; continue;}
int tmp = i - lst;
if (tmp < dif1) dif1 = tmp, a = lst, b = i;
if (tmp > dif2) dif2 = tmp, c = lst, d = i;
lst = i;
}
if (!lst || !dif2) puts("There are no adjacent primes.");
else printf("%lld,%lld are closest, %lld,%lld are most distant.\n", a, b, c, d);
}
return 0;
}