筛法shaifa

造出不超过正整数N的素数表的一个方法.最原始的筛法是在大约公元前250年由古希腊数学家厄拉多塞提出的.后来人们把它称为厄拉多塞筛法.它基于合数的下述简单性质：如果n≤N，而n是一个合数，则n必为一个不大于的素数所整除.厄拉多塞筛法的具体做法如下：先列出不超过的全体素数，.然后依次列出2,3,4,5，…，N.在其中留下p₁＝2，而把p₁的倍数全部划掉，再留下p₂＝3，而把p₂的倍数全部划掉，依此继续进行，直到最后留下pk，而把pk的倍数全部划掉.这时留下的整数就是不超过N的全体素数.例如取N=200，则不超过的全体素数是2,3,5,7,11,13.利用厄拉多塞筛法，我们可以造出不超过200的素数表(共有素数46个).因为这个方法像筛子一样，把合数筛掉而留下所有素数，所以叫做筛法.现有的素数表都是用这个方法略加变化造出来的.例如1914年莱梅发表了1到10 006 721的素数表(D.N.Lehmer,List of prime numbers from 1 to 10 006 721,Carnegie Institution,Washington 165 (1914)).1951年库利克等在此基础上又把它增加到10 999 997 (J.P.Ku-lik,L.Poletti and R.J.Porter,Liste des nombres premiersdu onzieme million (plus precisement de 10 006 721 a 10999 997),Amsterdam,1951). 自从有了电子计算机，更大得多的素数表也被造出来了.1959年，贝克尔和格伦贝尔格造出含有不超过104 395 301的全体素数(共6×10⁶个素数)的微型卡片.
厄拉多塞筛法经过改进和发展，已成为近代解析数论的重要工具之一.我国数学家陈景润在对筛法做了重大改进之后，使用深刻的解析方法，证明了关于哥德巴赫猜想的命题(1,2).参见“哥德巴赫猜想”.