埃氏筛

目录

• 埃氏筛
  • 目录
  • 1. 模板

---

1. 模板

#include <iostream>
using namespace std;

const int MAXN = 1e6 + 1;
int prime[MAXN];
bool visit[MAXN] = {0};

// 计算[2, n]内的素数
int E_sieve(int n)
{
    // 筛掉非素数
    for (int i = 2; i * i <= n; i++) {
        if (!visit[i]) {
            // 标记非素数
            for (int j = i * i; j <= n; j += i) {
                visit[j] = true;
            }
        }
    }
    // 统计素数的个数
    int k = 0;
    for (int i = 2; i <= n; i++) {
        if (!visit[i]) {
            prime[k++] = i;
        }
    }
    return k;
}

复杂度

$$O(n \log \log_2(n))$$