在数论 中，图兰筛法 （Turán sieve）是一个用以估计满足特定条件的“筛选过的”正整数 集大小的技巧，而这些条件一般都以同余 表示。这筛法由图兰·帕尔 于1934年发展。
图兰·帕尔
在筛法 的术语中，图兰筛法是一种“组合筛法”，也就是一种透过小心应用容斥原理 进行“筛选”的筛法。此种筛法可给出“筛选过的”的集合大小的上界。
设
A
{\displaystyle A}
x
{\displaystyle x}
P
{\displaystyle P}
A
p
{\displaystyle A_{p}}
A
{\displaystyle A}
P
{\displaystyle P}
p
{\displaystyle p}
d
{\displaystyle d}
P
{\displaystyle P}
A
d
{\displaystyle A_{d}}
A
{\displaystyle A}
d
{\displaystyle d}
A
1
{\displaystyle A_{1}}
A
{\displaystyle A}
设
z
{\displaystyle z}
P
(
z
)
{\displaystyle P(z)}
P
{\displaystyle P}
z
{\displaystyle z}
S
(
A
,
P
,
z
)
=
|
A
∖
⋃
p
∣
P
(
z
)
A
p
|
.
{\displaystyle S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .}
我们可以假定说在
d
{\displaystyle d}
p
{\displaystyle p}
|
A
d
|
{\displaystyle \left|A_{d}\right|}
|
A
p
|
=
1
f
(
p
)
X
+
R
p
{\displaystyle \left\vert A_{p}\right\vert ={\frac {1}{f(p)}}X+R_{p}}
而在
d
{\displaystyle d}
p
{\displaystyle p}
q
{\displaystyle q}
|
A
d
|
{\displaystyle \left|A_{d}\right|}
|
A
p
q
|
=
1
f
(
p
)
f
(
q
)
X
+
R
p
,
q
{\displaystyle \left\vert A_{pq}\right\vert ={\frac {1}{f(p)f(q)}}X+R_{p,q}}
其中
X
{\displaystyle X}
A
{\displaystyle A}
f
{\displaystyle f}
0
≤
f
(
d
)
≤
1
{\displaystyle 0\leq f(d)\leq 1}
设
U
(
z
)
=
∑
p
∣
P
(
z
)
f
(
p
)
.
{\displaystyle U(z)=\sum _{p\mid P(z)}f(p).}
S
(
A
,
P
,
z
)
≤
X
U
(
z
)
+
2
U
(
z
)
∑
p
∣
P
(
z
)
|
R
p
|
+
1
U
(
z
)
2
∑
p
,
q
∣
P
(
z
)
|
R
p
,
q
|
.
{\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 .}
哈代—拉马努金定理 ─一个正整数
n
{\displaystyle n}
ω
(
n
)
{\displaystyle \omega (n)}
正常阶
log
log
(
n
)
{\displaystyle \log {\log {(n)}}}
在高度的阶之下，几乎所有的整系数多项式都是不可约多项式 。
