图兰筛法

在筛法的术语中，图兰筛法是一种「组合筛法」，也就是一种通过小心应用容斥原理进行「筛选」的筛法。此种筛法可给出「筛选过的」的集合大小的上界。

设${\displaystyle A}$为不大于${\displaystyle x}$的正整数的集合，并假定${\displaystyle P}$为质数的集合，然后设${\displaystyle A_{p}}$是${\displaystyle A}$中可为${\displaystyle P}$中的质数${\displaystyle p}$整除的数组成的集合；此外，可设${\displaystyle d}$为${\displaystyle P}$中的不同质数的乘积，在这种状况下，可相应地定义${\displaystyle A_{d}}$为${\displaystyle A}$中可被${\displaystyle d}$整除的数的集合，并定义${\displaystyle A_{1}}$为${\displaystyle A}$本身。

设${\displaystyle z}$为任意实数，而${\displaystyle P(z)}$为${\displaystyle P}$中不大于${\displaystyle z}$的质数的乘积，那这筛法的目标就是估计下式：

${\displaystyle S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .}$

我们可以假定说在${\displaystyle d}$为质数${\displaystyle p}$的状况下，${\displaystyle \left|A_{d}\right|}$可由下式估计：

${\displaystyle \left\vert A_{p}\right\vert ={\frac {1}{f(p)}}X+R_{p}}$

而在${\displaystyle d}$为相异质数${\displaystyle p}$与${\displaystyle q}$的乘积状况下，${\displaystyle \left|A_{d}\right|}$可由下式估计：

${\displaystyle \left\vert A_{pq}\right\vert ={\frac {1}{f(p)f(q)}}X+R_{p,q}}$

其中${\displaystyle X}$是${\displaystyle A}$的元素个数，而${\displaystyle f}$则是一个使得${\displaystyle 0\leq f(d)\leq 1}$的函数。

设${\displaystyle U(z)=\sum _{p\mid P(z)}f(p).}$，可得下式：

${\displaystyle S(A,P,z)\leq {\frac {X}{U(z)}}+{\frac {2}{U(z)}}\sum _{p\mid P(z)}\left\vert R_{p}\right\vert +{\frac {1}{U(z)^{2}}}\sum _{p,q\mid P(z)}\left\vert R_{p,q}\right\vert .}$

• 哈代—拉马努金定理─一个正整数${\displaystyle n}$其相异的质因数个数${\displaystyle \omega (n)}$的正常阶为${\displaystyle \log {\log {(n)}}}$。
• 在高度的阶之下，几乎所有的整系数多项式都是不可约多项式。

• Alina Carmen Cojocaru; M. Ram Murty. . London Mathematical Society Student Texts 66. Cambridge University Press. : 47–62. ISBN 0-521-61275-6.
• Greaves, George. . Springer-Verlag. 2001. ISBN 3-540-41647-1.
• Halberstam, Heini; Richert, H.-E. . London Mathematical Society Monographs 4. Academic Press. 1974. ISBN 0-12-318250-6. MR 0424730. Zbl 0298.10026.
• Christopher Hooley. . Cambridge University Press. 1976: 21. ISBN 0-521-20915-3.