标签：mem   return   ems   提高   相同   eof   inline   cin   while   

数学模板

筛质数

素数筛

AcWing 196. 质数距离
给定两个整数L和U，你需要在闭区间[L,U]内找到距离最接近的两个相邻质数C1和C2（即C2-C1是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数D1和D2（即D1-D2是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

输入：每行输入两个整数L和U，其中L和U的差值不会超过1000000。

输出：对于每个L和U ，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）

如果L和U之间不存在质数对，则输出“There are no adjacent primes.”。

1≤L

题目给定的l，r的范围特别大，所以无法直接求出[l,r]中的素数，但我们发现任何一个合数n，肯定包括一个不超过\(\sqrt{n}\)的素数。所以根据这个性质，我们只需要2~\(\sqrt{r}\)之间的所有质数。然后，对于每一个质数p而言，我们可以标记i*p为合数(\(\frac{l}{p}\)≤i≤\(\frac{r}{p}\)),但这里的p不可以为1，要特判。

typedef long long LL;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void init(int n) {
    memset(st, 0, sizeof st);
    cnt = 0;
    for (int i = 2; i > l >> r) {
        init(50000);
        memset(st, 0, sizeof st);
        for (int i = 0; i = 2)
                primes[cnt ++ ] = i + l;
        if (cnt  primes[maxp + 1] - primes[maxp]) maxp = i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n",
                   primes[minp], primes[minp + 1],
                   primes[maxp], primes[maxp + 1]);
        }
    }
    return 0;
}

acwing提高课数学模板

标签：mem   return   ems   提高   相同   eof   inline   cin   while   

原文地址：https://www.cnblogs.com/QingyuYYYYY/p/12460554.html