P1835 素数密度

一、枚举约数

想到欧拉筛，然而我们并不能筛到(2e9)，时间上C++每秒能算(1e9),(2e9)次循环肯定狒狒了。

空间上也不允许开那么大的数组，数组最大我试过(2e8)能开,其实这都完全没有必要。因为(1e8)就是(4*100000000=400000000byte=381MB)，而NOIP一般是限制(128MB)，所以(1e8)都太大了。

看来祼的欧拉筛是搞不定这道题了，也是，绿题嘛，没点难度还成？

想想办法，因为(2e9)范围内的质数因子最大也到不了(50000)(用计算器或者(C++)代码(sqrt)一下(INT32_MAX)就知道结果~)，我们可以预处理出(2sim 50000)以内的素数，然后对于每一个数，筛出质因子的倍数，剩下的就是区间内的质数啦，放一下代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 50010;
int l, r;
//答案
int ans;

//欧拉筛
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];             // st[x]存储x是否被筛掉
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    //优化一下
    ios::sync_with_stdio(false);
    cin.tie(0);

    //求出50000以内的质数:sqrt(INT32_MAX)=46341
    get_primes(N);

    //读入左右边界
    cin >> l >> r;

    //第十一个测试点是后加上的，导致有1 3这样的测试用例
    if (l < 2)l = 2;

    //开始遍历所有数字，判断是不是已知质数区间的倍数
    for (int i = l; i <= r; i++) {
        //是不是质数
        bool f = false;
        //k是i的质数因子上限
        int k = sqrt(i);
        //遍历已经筛出来的质数数组，从第一个2开始，到k结束
        for (int j = 0; primes[j] <= k; j++) {
            //i:区间内的每个数字
            //j:primes[j]代表每一个可能的质数因子
            //如果能被某个质数整除，并且它不是质数因子。那么它就是合数
            if (i % primes[j] == 0 && i / primes[j] > 1) {
                f = true;
                break;//是合数就不用再继续尝试了
            }
        }
        if (!f)ans++;
    }
    //输出结果
    cout << ans << endl;
}

总结一下上面的代码：
1、(l sim r)之间的数字可以被(（1sim sqrt{l}）)和(（1sim sqrt{r}）)之间的整数筛掉，因为这部分是小因子，判断小因子后，大因子那边就不用管了。

2、外层循环在讨论((l sim r))之间的每个数字，内层循环讨论的在已经筛出的质数数组，范围是(2sim primes[j]<=k),看看(i)这个数字，是不是可以被当前的质数整除，（还不能和质数相等，这个条件要注意），如果能整除，它是合数，如果所以可能的质数因子讨论完，还没有找到可以整除的，说明(i)是质数，(ans++)。

此办法，有一个测试点TLE掉，得了91分。

第10个测试点数据下载回来，看到:

2146483647 2147483647

果然够狠！数字这么大，如果按上面的思路，每次都从(2sim sqrt{2147483647})确实时间太长，超时也可以理解了。

那该怎么办才好呢？我陷入到思考中...,上面的代码是枚举约数，超时，如果要枚举质数倍数呢？会不会有效果？

数学知识储备
【大于L,并且是p的倍数,最小整数是多少?】

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    //数学知识储备
    //【大于L,并且是p的倍数,最小整数是多少?】
    int p = 3;
    for (LL L = 100; L <= 200; L++)
        cout << max(2ll, (L - 1) / p + 1) * p << endl;
    return 0;
}

二、枚举倍数

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

//欧拉筛
const int N = 1e5 + 10;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];             // st[x]存储x是否被筛掉
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

//区间范围,因为我们无法完全映射所有的区间，只能采用类似于偏移的办法对某段区间整体偏移L进行描述。
//否则空间上的限制就先达到了，无法用计算机模拟了。
const int M = 10000010;
int a[M];//记录偏移后的数据是不是合数，1：合数；0：质数。a[i]表示L+i是不是合数, 有一个偏移量L

int main() {
    //筛出50000之内的所有质数
    get_primes(50000);//R开根号的极限也小于50000
    //问：为啥要开LL，开INT不行吗？
    //答：不行，因为下面的运算中可能存在加法，如果是极限的整数，再加一下就会爆INT。
    LL L, R;
    cin >> L >> R;
    //特判，防止第11个测试点WA掉。
    if (L == 1) L = 2;

    //遍历已知的质数列表
    for (int i = 0; i < cnt; i++) {
        //start：找到开始筛的数字
        //【大于L,并且是p的倍数,最小整数是多少?】
        LL start = max(2ll, (L - 1) / primes[i] + 1) * primes[i];
        //成倍的质数筛出掉
        for (LL j = start; j <= R; j += primes[i]) a[j - L] = 1; //标识为质数
    }

    //结果
    int ans = 0;
    for (LL i = L; i <= R; i++) if (!a[i - L])ans++;
    printf("%d", ans);
    return 0;
}

P1835 素数密度

一、枚举约数

二、枚举倍数

相关推荐