欧拉筛 / 线性筛

一句话理解

线性筛每个合数只被最小质因子划一次。

为什么要学

O(n)。

讲解

primes 列表，遇 i%p==0 break。

例子

欧拉筛。同时可求 phi、mu、最小质因子。

常见错误

• 不 break 失去线性。
• n=1e8 内存。