POJ2689 Prime Distance

思路

• 题目给出[l, u], 先求[2, sqrt(u)]之间的素数，然后利用[2, sqrt(u)]之间的素数的倍数筛掉[l, u]中的合数
• 上面两步可以在欧拉筛法的函数中一起实现，即：找到一个素数$i$，就把$i$的在$[l, u]$之间的倍数筛掉
• 注意：找到素数$i$后，枚举$i$的倍数要如下实现(不要把$l$看成$1$了，是$l/i$)。如果j从2开始，会TLE；j不定义成LL，会RE：

for (LL j = l / i; j * i <= u; j++)
    {
        if (j > 1 && j * i - l >= 0)
        {
            st2[j * i - l] = true;
        }
    }

• 两组样例：

2146483648 2147483647
2146483811,2146483813 are closest, 2146841093,2146841273 are most distant.
1 2
There are no adjacent primes.

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
typedef long long LL;

const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N], st2[N];
int l, u;

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            for (LL j = l / i; j * i <= u; j++)
            {
                if (j > 1 && j * i - l >= 0)
                {
                    st2[j * i - l] = true;
                }
            }
        }
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                break;
            }
        }
    }
}

int main()
{
    while (scanf("%d%d", &l, &u) != EOF)
    {
        if (l == 1)
        {
            l = 2;
        }

        cnt = 0;
        memset(st, 0, sizeof st);
        memset(st2, 0, sizeof st2);

        int sqr = (int)sqrt(u) + 1;
        get_primes(sqr);

        cnt = 0;
        for (LL i = 0; i < u - l + 1; i++)
        {
            if (!st2[i])
            {
                primes[cnt++] = i;
            }
        }

        int res_min = 1e9, res_max = -1;
        int min_idx = 0, max_idx = 0;
        if (cnt >= 2)
        {
            for (int i = 0; i < cnt - 1; i++)
            {
                if (primes[i + 1] - primes[i] > res_max)
                {
                    res_max = primes[i + 1] - primes[i];
                    max_idx = i;
                }
                if (primes[i + 1] - primes[i] < res_min)
                {
                    res_min = primes[i + 1] - primes[i];
                    min_idx = i;
                }
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", primes[min_idx] + l, primes[min_idx + 1] + l, primes[max_idx] + l, primes[max_idx + 1] + l);
        }
        else
        {
            puts("There are no adjacent primes.");
        }
    }

    return 0;
}