埃氏筛

一句话理解

埃氏筛：每找到质数划掉它的倍数。

为什么要学

O(n log log n) 筛 1..n。

讲解

从 i*i 开始划。

例子

for (int i = 2; i <= n; i++) if (!vis[i]) {
    for (int j = i; (long long)i * j <= n; j++) vis[i * j] = 1;
}

质数的倍数都是合数。

常见错误

• j 从 i 还是 2 重复划。可从 i*i。
• n=1e7 还每次分解。