POJ 2689

题目大意

暂无

题目解法

暂无

RTFC

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