本节部分内容译自博文 Решето Эратосфена 与其英文翻译版 Sieve of Eratosthenes。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。
素数筛法如果我们想要知道小于等于 \(n\) 有多少个素数呢？
一个自然的想法是对于小于等于 \(n\) 的每个数进行一次质数检验。这种暴力的做法显然不能达到最优复杂度。
埃拉托斯特尼筛法考虑这样一件事情：如果 \(x\) 是合数，那么 \(x\) 的倍数也一定是合数。利用这个结论，我们可以避免很多次不必要的检测。
如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
int Eratosthenes(int n) { int p = 0; for (int i = 0; i <= n; ++i) is_prime[i] = 1; is_prime[0] = is_prime[1] = 0; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { prime[p++] = i; // prime[p]是i,后置自增运算代表当前素数数量 if ((long long)i * i <= n) for (int j = i * i; j <= n; j += i) // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i // 的倍数开始，提高了运行速度 is_prime[j] = 0; // 是i的倍数的均不是素数 } } return p; }以上为 Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法），时间复杂度是 \(O(n\log\log n)\)。
怎么证明这个复杂度呢？我们先列出复杂度的数学表达式。
发现数学表达式显然就是素数的倒数和乘上 \(n\)，即 \(n\sum_p {\frac{1}{p}}\)。
我们相当于要证明 \(\sum_p {\frac{1}{p}}\) 是 \(O(\log\log n)\) 的。我们考虑一个很巧妙的构造来证明这个式子是 \(O(\log\log n)\) 的：
证明：
注意到调和级数 \(\sum_n {\frac{1}{n}}=\ln n\)。
而又由唯一分解定理可得：\(\sum_n {\frac{1}{n}}=\prod_p {(1+\frac{1}{p}+\frac{1}{p^2}+\cdots)}=\prod_p {\frac{p}{p-1}}\)。
我们两边同时取 \(\ln\)，得：
\[\begin{aligned} \ln \sum_n {\frac{1}{n}}&=\ln \prod_p {\frac{p}{p-1}}\\ \ln\ln n&=\sum_p {(\ln p-\ln {(p-1)})} \end{aligned} \]