素数筛模板

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
#include<iostream>

using namespace std;

typedef long long ll;

const int N = 2e7+10;

int prime[N];
bool vis[N];
long long idx = 0;

void aishi(){
    for(ll i = 2; i < N; i++){
        if(!vis[i]) {
            prime[idx++] = i;
            for(ll j = i*i; j < N; j+=i){
                vis[j] = true;
            }
        }
    }
}

int main()
{
    aishi();
    cout << idx << endl;
    for(int i = 0; i < idx; i++){
        cout << prime[i] << ' ';
    }
}

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
#include<iostream>

using namespace std;

typedef long long ll;
const int N = 2e7+10;

int prime[N];
bool vis[N];
long long idx = 0;

void oula(){
    for(ll i = 2; i < N; i++){
        if(!vis[i]) prime[idx++] = i;
        for(int j = 0; j < idx && i*prime[j] < N; j++){
            vis[i*prime[j]] = true;
            // i 能被prime[j] 整除代表 i 是 prime[j] 的倍数
        	// 换言之，i 之前被 prime[j] 筛过了
        	// 由于 prime 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
        	// prime[j] 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break 掉就好了
            if(i % prime[j] == 0) break;
        }
    }
}

int main()
{
    oula();
    cout << idx << endl;
    for(int i = 0; i < idx; i++){
        cout << prime[i] << ' ';
    }
}