素数筛法(sieve of primer number)

 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
38
39
40

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-06-21 12:35:06
 * 最后修改: 2025-03-01 10:41:52
 * 文件描述:  埃氏筛素数  O(nloglogn)
****************************************************************/

#include <iostream>
#include <cmath>
using namespace std;
 
const int maxn = 1000000;
bool isPrimer[maxn];    // i是合数isPrimer[i]为1，i是素数，isPrimer[i]为0
 
void sieve(long long n){
    int m = sqrt(n);
    isPrimer[2] = 0;
/*
从i*i开始筛选，小于i的数在之前的循环已经筛过，比如6是在i=2时候筛过了，所以j=3时就从3*3开始。
另外，由于i筛选的时候可能会重复前面已经筛过的，比如18，就是在i=2和3时，都筛一遍。
*/
    for (long long i = 2; i <= m; i++) {
        if (!isPrimer[i]){
            for (long long j = i * i; j <= n; j += i){
                isPrimer[j] = 1;
            }
        }
    }
}
 
int main(){
    long long n;
    cin >> n;
    sieve(n);
    for (long long i = 2; i < n; i++){
        if (isPrimer[i] == 0) cout << i << ' ';
    }
       
return 0;
}

 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

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-06-21 20:39:52
 * 最后修改: 2025-03-01 11:52:29
 * 文件描述: 线性筛素数  O(n)
****************************************************************/
// 线性筛法是从小到大筛选，但是每个数只会被最小质因子筛选一次。

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100000001;
vector<bool> visited(MAXN, false); // 标识数组，visited[i] = true 说明 i 是合数
vector<int> prime; // 存储质数的数组

int main() {
    int n;
    cin >> n;

    for (int i = 2; i <= n; i++) {
        if (!visited[i]) {
            prime.push_back(i); // 如果 i 是质数，添加到 prime 数组中
        }
        // 从最小的质数开始枚举
        for (int j = 0; j < prime.size() && prime[j] * i <= n; j++) {
            int k = prime[j];
            visited[i * k] = true; // 标记合数
            // 如果 i 是质数，当 k = i 时，退出
            // 如果 i 是合数，当 k 等于 i 的最小质因子时退出
            if (i % k == 0) break;
        }
    }

    cout << prime.size(); // 输出质数的个数
    return 0;
}