[题] 筛质数 #质数（素数）

题目

AcWing 868. 筛质数

---

题解

方法一：朴素筛法 及其优化：埃氏筛

[笔记] 筛素数——朴素筛法及其优化：埃氏筛法 #质数（素数）

方法二：线性筛法求质数

[笔记] 线性筛质数（素数）

---

代码

线性筛：

#include
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n ){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}
int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21