Sieve

考虑如何筛出 \(n\) 以内的所有素数，显然有一个最简单的想法，即将所有已求出的质数的倍数标记，表示它们不为质数，并且从小到大遍历到数 \(i\) 时，若它没有被标记，则 \(i\in Prime\)。 在此算法中，每个数都被自己所有本质不同的质因子筛了一次，所以总复杂度为 \(\Theta(n\ln \ln n)\)。