筛法

---

数论的重要方法，是解决哥德巴赫猜想等著名数论问题的强有力工具。

为了解决不同的数论问题，人们创造出各种不同的筛法，从古老的爱拉托士散纳筛法到薛尔伯格筛法，直至近代深刻的组合筛法和大筛法等等。

公元前3世纪，就有了爱拉托士散纳筛法，它是专门用于制造素数表的，它的理论根据是以下这样一个十分简单的原理，即所有小于或等于N的合数必定为不超过的某个素数所整除。因此在到N之间的所有自然数中，只要划去为不超过的素数所整除的数以后，留下的就是到N之间的全部素数，这里的N当然是指大于或等于4的自然数。例如，由于10以下的全部素数为2，3，5，7。

因此在10到100之间的整数中，依次将被2除尽的数、被3除尽的数、被5除尽的数，以及被7除尽的数都划去以后，留下的正好就是10到100之间的所有素数。在这里，2，3，5，7这4个素数好象组成了一个“筛子”，凡是能被这“筛子”中一个数除尽的数就要被“筛”掉，而不能被这“筛子”中任何一个数除尽的数就留下，通过这个“筛子”，“筛”出了10到100之间的所有素数，这就是最古典的“筛法”，即爱拉托士散纳“筛法”。

一般地，“筛子”可以由满足一定条件的有限个素数所组成，而被“筛”选的对象可以是一个由有限多个整数组成的数列，若以A表示一个满足一定条件的由有限多个整数组成的集合，以P表示一个满足一定条件的无限多个不同的素数组成的集合，Z≥2为任一正数。令，且以S(A；P，Z)表示集合A中所有与P_(z)互素的元素的个数，即

这里P_(z)就是一个“筛子”，凡是和它不互素的数都被“筛”掉，而和它互素的数将被留下，因而S(A；P，Z)就是集合A经过“筛子”P_(z)“筛选”后所“筛剩”的元素的个数，一般称S(A；P，Z)为筛函数，筛法就是研究筛函数的性质与作用的一种方法，它的基本问题就是要估计筛函数S(A；P，Z)的上界和正的下界。

筛法可以用来研究数论中的许多问题，这些问题主要是关于一个整数数列中具有某种性质的整数是否存在及其个数的多少。例如，应用筛法，可以大概知道任意两个正数X和Y之间的素数个数有多少，这就是著名的素数分布问题；再如，设N为一大偶数，取集合A=A(N)=｛n(N－n)，1≤n≤N｝，P为所有素数组成的集合，再设λ≥2，取Z=N^1／λ。

若能证明S(A；P，N^1／λ)＞0，则就证明了命题(a，a)，这里的a是：当λ是正整数时，a=λ－1，与λ不是正整数时，a=〔λ〕，若当λ=2时，S(A；P，N^1／λ)＞0，则就等于证明了命题(1，1)成立，即哥德巴赫猜想成立。