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

图兰·帕尔

描述

编辑

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

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

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

 

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

 

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

 

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

 ,可得下式:

 

应用

编辑

参考资料

编辑