Si_Yue小屋
0%

筛法

发表于 分类于

筛法

  1. 埃氏筛法

筛掉质数的倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef long long LL;

vector<LL> is_prime,prime;

LL sieve(int n){
    is_prime=vector<LL>(n+1,1);
    is_prime[0]=is_prime[1]=0;
    for(LL i=2;i<=n;++i){
        if(is_prime[i]){
            prime.push_back(i);
            for(LL j=i*i;j<=n;j+=i){
                is_prime[j]=0;
            }
        }
    }
    return prime.size();
}

分块优化空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int count_primes(int n){
    const int S=1e4;
    int ret=0;
    //筛sqrt(n)中的质数并记录
    vector<int> primes;
    int nsqrt=sqrt(n);
    vector<bool> isprime(n+1,true);
    for(int i=2;i<=nsqrt;++i){
        if(isprime[i]){
            primes.push_back(i);
            for(int j=i*i;j<=n;j+=i){
                isprime[j]=false;
            }
        }
    }
    //分块计数
    vector<bool> block(S);
    for(int k=0;k*S<=n;++k){
        block=vector<bool>(S,true);
        int start=k*S;
        for(int p:primes){
            //找不小于start的最小的p的倍数，先找是p的多少倍
            int start_idx=(start+p-1)/p;
            //若start_idx小于p，则已经被筛选过
            int j=max(start_idx,p)*p-start;
            for(;j<S;j+=p){
                block[j]=false;
            }
        }
        //0和1不是质数
        if(k==0)block[0]=block[1]=false;
        for(int i=0;i<S&&start+i<=n;++i){
            if(block[i])ret++;
        }
    }
    return ret;
}
  1. 欧拉筛法（线性筛）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<int> primes;
vector<bool> isprime;

int euler(int n){
    isprime=vector<bool>(n,true);
    for(int i=2;i<=n;++i){
        if(isprime[i]){
            primes.push_back(i);
        }
        //考虑当前数对已加质数的乘积
        for(int p:primes){
            if(1ll*p*i>n)break;
            isprime[p*i]=false;
            if(i%p==0)break;
            //由于primes里面质数是从小到大的，
            //所以i乘上其他的质数的结果一定会被
            //当前prime的元素的倍数筛掉，
            //就不需要在这里先筛一次，
            //所以这里直接 break掉就好了
            //此时p是i的最小的质因子
            //换句话说，(i*p)=i * p=更小的i * 更大的p，只要更新一遍就好了
        }
    }
    return primes.size();
}
  1. 线性筛求解欧拉函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int MAXN=5e6;

vector<bool> isprime(MAXN,1);
vector<int> primes,phi(MAXN,0);

void pre(){
    for(int i=2;i<=MAXN;++i){
        if(isprime[i]){
            primes.push_back(i);
            phi[i]=i-1;
        }
        for(int p:primes){
            if(i*p>MAXN)break;
            isprime[i*p]=false;
            if(i%p){
                //p!|i,则(p,i)=1,则由积性函数可拆解
                phi[i*p]=phi[i]*phi[p];
            }else{
                //p|i,则i包含i*p的所有质因子,拆解(i*p)=i * p,此时p是i最小的质因子
                phi[i*p]=phi[i]*p;
                break;
            }
        }
    }
}