素数筛与区间筛

埃式筛法展开目录

给定一个正整数 n (n <= 1e6)，请问 n 以内有多少个素数？

做法其实很简单，首先将 2 到 n 范围内的所有整数写在一张一维表里，其中 2 是最小的素数。将表中所有 2 的倍数划去，此时表中剩下的最小的数字是 3，3 无法被更小的数整除，所以 3 是素数。再将表中所有 3 的倍数划去...... 以此类推，如果表中剩余的最小数是 m，则 m 就是素数，将表中所有 m 的倍数划去，这样反复操作，就能依次枚举 n 以内的素数，时间复杂度为 $O (nloglogn)$

int prime[MAXN];
bool is_prime[MAXN];

//返回n以内的素数个数 
int sieve(int n) {
    int p = 0;
    for (int i = 2; i <= n; ++i)
        is_prime[i] = true;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime[p++] = i;
            for (int j = 2 * i; j <= n; j += i)
                is_prime[j] = false;
        }    
    }
    return p;
}

区间筛法展开目录

给定整数 a 和 b，请问区间 $[a,b)$ 内有多少个素数？（$a < b \leq 10^{12},b-a \leq 10^6$）

因为 b 以内合数的最小质因数一定不会超过 $\sqrt {b}$，因为如果存在 $d$ 是 $n$ 的约数，那么 $n/d$ 也是 $n$ 的约数，由 $n = d \times n/d$ 可知 $min (d,n/d)\leq \sqrt {n}$

如果有 $\sqrt {n}$ 以内的素数表的话，就可以把埃式筛法用在 $[a,b)$ 上了。也就是说，先分别做好 $[2,\sqrt {b})$ 的表和 $[a,b)$ 的表，然后从 $[2,\sqrt {b})$ 的表中筛得素数的同时，也将其倍数从 $[a,b)$ 的表中筛去，最后剩下的就是区间 $[a,b)$ 内的素数了

假如要求 [1e9,1e9+2) 区间内的素数，难道我们要开 1e9+3 大小的数组吗？其实并不用，我们利用下标偏移，可以减少空间开销。即将 [1e9,1e9+2) 对应到 [0,2)，整体区间向左偏移 1e9

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e5;
bool is_prime[MAXN];
bool is_prime_small[MAXN];
ll prime[MAXN];
ll prime_num = 0;

//对区间[a,b)内的整数执行筛法，is_prime[i-a]=true <=> 表示i是素数（下标偏移了a） 
void segment_sieve(ll a, ll b) {
    for (ll i = 0; i * i < b; i++) //对[2,sqrt(b))的初始化全为质数
        is_prime_small[i] = true;
    for (ll i = 0; i < b - a; i++) //对下标偏移后的[a,b)进行初始化
        is_prime[i] = true;
        
    for (ll i = 2; i * i < b; i++) { //筛选[2,sqrt(b))
        if (is_prime_small[i]) {
            for (ll j = 2 * i; j * j < b; j += i) 
                is_prime_small[j] = false;
            //(a+i-1)/i 得到最接近a的i的倍数，最低是i的2倍，然后筛选
            for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i)
                is_prime[j - a] = false;
        }
    }
    for (ll i = 0; i < b - a; i++) //统计个数 
        if (is_prime[i])
            prime[prime_num++] = i + a;
}

int main() {
    ll a, b;
    while (~scanf("%lld%lld", &a, &b)) {
        prime_num = 0;
        memset(prime, 0, sizeof(prime));
        segment_sieve(a, b);
        printf("%lld\n", prime_num);
    }
    return 0;
}