首页 程序设计 小学数学

# 埃氏筛

时间复杂度 O(N⋅log(log(N)))O(N·log(log(N)))

C++
1
2
3
4
5
6
7
void init(int n) {
    notPrime[1] = 1;
    for (int i = 2; i * i <= n; i++)
        if (!notPrime[i])
            for (int j = i * i; j <= n; j += i)
                notPrime[j] = 1;
}

# 线性筛（欧拉筛）

埃氏筛在筛的过程中，合数会被重复筛到，引入线性筛（欧拉筛），可以在 O(N)O(N) 的时间内完成

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void init(int n) {
    notPrime[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (!notPrime[i])
            prime.push_back(i);
        for (auto p : prime) {
            if (p * i > n)
                break;
            notPrime[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
}