sieve of Eratosthenes

《初等数论》 · 第 13 页

这种寻找不可约数的方法，通常叫做 Eratosthenes 筛法。

由 admin 提交

《LECTURE NOTES IN ANALYSIS (2011)》 · 第 408 页 · Notes on Chapter 8，§8.3

For example, by the sieve of Eratosthenes we know that if $q=\prod_{p\le\sqrt{x}}p$, then the number of integers $n\le x$ such that $(n,q)=1$ is $\pi(x)-\pi(\sqrt{x})+1$.