素数筛与区间筛

埃式筛法

给定一个正整数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;
}