跳转到内容

图兰筛法

维基百科,自由的百科全书
图兰·帕尔

数论中,图兰筛法(Turán sieve)是一个用以估计满足特定条件的“筛选过的”正整数集大小的技巧,而这些条件一般都以同馀表示。这筛法由图兰·帕尔于1934年发展。

描述

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

为不大于的正整数的集合,并假定为质数的集合,然后设中可为中的质数整除的数组成的集合;此外,可设中的不同质数的乘积,在这种状况下,可相应地定义中可被整除的数的集合,并定义本身。

为任意实数,而中不大于的质数的乘积,那这筛法的目标就是估计下式:

我们可以假定说在为质数的状况下,可由下式估计:

而在为相异质数的乘积状况下,可由下式估计:

其中的元素个数,而则是一个使得的函数。

,可得下式:

应用

参考资料