AcWing 196 质数距离（素数，筛法）

问题：给定L，R，找出[L,R]中距离最近和最远的质数对。

分析：注意到L，R的范围很大，到了int极限值，问题毫无疑问是筛质数，不能用普通的筛法筛出[1,R]（复杂度）。

埃氏筛法本质是倍数标记合数，注意到如果x是合数，那它一定有不大于sqrt(x)的因数y，那么x就可以被y倍数标记。

步骤：

1.埃氏筛找出[1,sqrt(R)]中的质数。（初始化）

2.用这些质数将[L,R]中的合数进行倍数标记。

3.找出[L,R]中的质数更新答案。

注意细节：

1.枚举倍数j要大等于2，即不能把质数i本身标记了。

2.不开longlong见祖宗（接近int极限就开longlong）。

3.特判（1和0既不是质数也不是合数）。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int L, R, tot, a[N], cnt, b[N];
bool v[N];
signed main() {
    for (int i = 2; i <= 1e6; i ++) {
        if (v[i]) continue;
        a[++ tot] = i;
        for (int j = 2; j * i < 1e6; j ++) v[i * j] = 1;
    }
    while (cin >> L >> R) {
        memset(v, 0, sizeof(v));
        memset(b, 0, sizeof(b)); cnt = 0;
        for (int i = 1; i <= tot; i ++) {
            if (a[i] > sqrt(R)) break;
            int j = (L % a[i] != 0) ? L / a[i] + 1 : L / a[i];//向上取整 
            j = max(j, (long long)2);
            for (j; a[i] * j <= R; j ++) v[a[i] * j - L] = 1; 
        }
        for (int i = L; i <= R; i ++) { 
            if (v[i - L] || i == 1) continue;//特判1 
            b[++ cnt] = i;
        }
        if (cnt < 2) {
            printf("There are no adjacent primes.\n");
            continue;
        }
        int mx = 0, mn = N;
        int X1, X2, Y1, Y2;
        for (int i = 2; i <= cnt; i ++) {
            int res = b[i] - b[i - 1];
            if (res < mn) {
                mn = res;
                X1 = b[i - 1], X2 = b[i];
            }
            if (res > mx) {
                mx = res;
                Y1 = b[i - 1], Y2 = b[i];
            }
        }
        printf("%d,%d are closest, %d,%d are most distant.\n", X1, X2, Y1, Y2);
    }
    return 0;
}