欧拉筛和区间筛

　　

首先介绍一下线性筛，之所以称之为线性筛是因为它的复杂度为O(n)。

　　与埃氏筛相比，欧拉筛不会对已经被标记过的合数再进行重复标记，它们保证每个合数只会被它的最小质因数筛去故效率更高。欧拉筛将合数分解为 (最小质因数 * 一个合数) 的形式，通过最小质因数来判断当前合数是否已经被标记过。

　　2020-03-03-17:56:55

　　我现在才知道循环最后为什么 i % prime[j] == 0 时要break；

　　　　因为此时，如果i % prime[j] == 0, i = k * prime[j] 。i * prime[j + 1] = k * prime[j] * prime[j + 1]，k肯定大于等于二，也就是说k * prime[j] > prime[j + 1]，也就是说prime[j] 不是i * prime[j]的最小质因子，反而是prime[j + 1]。

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 10000, n = 2000;
bool isvisited[maxn];
int prime[n];
int cnt;

int main () {
    for(int i = 2; i < maxn; i ++) {
        if(!isvisited[i])
            prime[cnt ++] = i;
        for(int j = 0; j < cnt; j ++) {
            if(i * prime[j] > maxn) break;
            isvisited[i * prime[j]] = true;//每个合数都被他的最小质因数标记
            if(i % prime[j] == 0)   break; //当发现某个合数存在更小的质因数时就停止标记
        }
    }
    for(int i = 0; i < cnt; i ++)   
        printf("%d	", prime[i]);
    return 0;
}

接着再介绍一下素数的区间筛法。

　　给定整数a和b，请问区间[a,b)内有多少个素数？ a<b<=10^12，b-a<=10^6。因为b以内合数的最小质因数一定不超过sqrt(b),如果有sqrt(b)以内的素数表的话，就可以把线性筛用在[a,b)上了,

先分别做好[2,sqrt(b))的表和[a,b)的表，然后从[2,sqrt(b))的表中筛得素数的同时，也将其倍数从[a,b)的表中划去，最后剩下的就是区间[a,b)内的素数了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
bool is_prime[maxn], is_prime_small[maxn];
ll prime[maxn];
ll prime_num = 0;

//对区间[a, b)的整数执行筛法，is_prime[i - a] = true <=> i 是素数
void segment_sieve(ll a, ll b) {
    for(int i = 0; (ll)i * i < b; i ++)  is_prime_small[i] = true;//对[2, sqrt(b)]进行初始化
    for(int i = 0; i < b - a; i ++)  is_prime[i] = true;
    for(int i = 2; (ll)i * i < b; i ++) {
        if(is_prime_small[i]) {
            for(ll j = 2 * i; (ll)j * j < b; j += i)    is_prime_small[j] = false;//筛[2, sqrt(b))
            for(ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i)    is_prime[j - a] = false;//筛[a,b)
        }
    }
    for(ll i = 0; i < b - a; i ++)
        if(is_prime[i]) prime[prime_num ++] = i + a;
}

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