1. 朴素筛
$\quad$ O(nlogn),无脑标记一切数的倍数,存在大量重复计算。
2. 埃氏筛
$\quad$ O(nloglogn), 相比朴素筛法,不标记合数的倍数,只标记质数的倍数。但依然存在重复标记,如,标记2的倍数时, $12 = 6 * 2$, 标记3的倍数时,$12 = 4 * 3。$
3. 线性筛
$\quad$ O(n),记录最小质因子,核心思想是:x仅会被其最小质因子筛去。
$\quad$ 具体来说,考虑小于i的所有质数 $primes[j]$,那么$primes[j]$就是 $primes[j] * i$ 的最小质因子,并将 $primes[j] * i$ 筛去。
$\quad$ 当 $i \% primes[j] == 0$ 时必须终止,假设不终止,那么 $i * primes[j + 1]$ 的最小质因子并不是 $primes[j + 1]$,如 $12 = 2 * 6$最小质因子为2, 但$18 = 3 * 6$最小质因子并不是3,而是2。