登录以参加训练计划

课件

线性筛法（欧拉筛法）

基本思想

线性筛法（欧拉筛法）可以在 O(n) 的时间复杂度内筛选出 n 以内的所有素数。

算法原理

const int MAXN = 1e7 + 5, MR = 1e6 + 5;
bool isprime[MAXN];
int prime[MR];

void init() {
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for (int i = 2; i <= MAXN; i++) {
        if (isprime[i]) {
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= MAXN; j++) {
            isprime[i * prime[j]] = false;
            if (i % prime[j] == 0) break;
        }
    }
}

关键点

• prime[0] 存储素数的个数
• 每个合数只被它的最小质因子筛一次
• 时间复杂度 O(n)