跳转到内容

更大筛法

维基百科,自由的百科全书

在数论中,更大筛法(larger sieve)是一个由帕特里克·X·加拉格尔英语Patrick X. Gallagher发明的筛法,其名称表明这是一种大筛法塞尔伯格筛法之类的组合筛法在只移除数个同余类时能得到最强的结果;而大筛法之名表明了这类的筛法能移除大量、多达半数的同余类;而更大筛法则是一个可移除任意多同余类的筛法。

描述

[编辑]

假定是一个质数及其幂次所组成的集合、是一个整数、该区间当中的整数的集合,且对于而言,至多只有个包含的元素的模同余类的话,那么有以下关系式:

上式中,右侧的分母为正数。[1]

应用

[编辑]

根据加拉葛的结果,更大筛法用于下列大筛法失效的状况,尤其适用于的状况:[2]

使得对所有质数而言,的阶的数的数量。

假若排除掉的模同余类的数量随变化的话,那么更大筛法常会与大筛法结合使用。其中更大筛法会用于如上定义的以做为许多同余类被移除掉的集合;而大筛法则用套用在落于之外的质数上,以得这些质数的资讯。[3]

注解

[编辑]
  1. ^ Gallagher 1971, Theorem 1
  2. ^ Gallagher, 1971, Theorem 2
  3. ^ Croot, Elsholtz, 2004

参考资料

[编辑]