素数分布的一种新筛法

管训贵

（泰州师范高等专科学校 数理系，江苏泰州 225300）

素数分布的一种新筛法

管训贵

（泰州师范高等专科学校 数理系，江苏泰州 225300）

通过给出奇合数的分解公式，揭示了奇合数与奇素数的构成规律，并在此基础上提出了寻求素数分布的一种简便易行的新筛法。

奇合数；奇素数；分解公式；筛法

1 引言

素数的性质及其分布是数论研究的核心内容之一。国外许多数论专家，如：P. Fermat、Eratosthenes、Euler、C. Goldbach、J. Wilson、V. Brun、D. N. Lehmer、J. E. Littlewood、E. Landau、D. Hilbert、G. H. Hardy、J. Hadamard等长期从事这一领域的研究工作[1,2]。我国数学家华罗庚、陈景润、王元、潘承洞、潘承彪等也都有许多建树[3-7]。尤其是陈景润教授于1966年对筛法作了新的重要改进之后，在解决哥德巴赫猜想的问题上取得了重大的突破，他证明了“每一个充分大的偶数都是一个素数与一个素因数个数不超过 2的殆素数之和”[8]。尽管如此，这一领域的研究已进入“山重水复疑无路”的境地。文[9]给出了一种筛法，其计算步骤仍比较繁琐复杂。本文另辟蹊径，提出寻求素数分布的一种简便易行的新筛法。

2 奇合数与奇素数的构成规律

正整数不是奇数便是偶数，而奇数又可分为奇合数与奇素数两大类。设m是奇合数，则m必有分解式

其中i,j均为正整数。由此可以推出奇合数与奇素数的构成规律如下：

定理1 设i,j为正整数，对于给定的不小于9的整数N，若

则(2i + 1)(2j+1)取遍不小于9而不超过N的全体奇合数；并且 (2i+ 1)(2 j+1)除9到N之间的奇合数外，无其它数。

证明 由算术基本定理知，任一不小于9且不超过N的奇合数A均可表示为

这里pt是互异的奇素数，at为正整数，t =1,…,k，k≥2。

由(1)知任意一个奇合数均可表示为 (2i+1)(2 j +1)的形式。换言之，不小于 9且不超过N的奇合数全部包含在(2i+ 1)(2j+1)中。

另一方面， (2i+ 1)(2 j+1)仅包含不小于9且不超过N的奇合数。事实上， (2i+ 1)(2 j+1)首先是奇数，其次不可能是素数（因为有 2a+1＞1和 2b+ 1＞ 1两个因数）。既是奇数又非素数的数必是奇合数。

定理1得证。

定理2 对任意的正整数i,j，若正整数

则

为奇素数；否则，

为奇合数。

证明 假设

表示奇合数，则存在正整数u,v，使

即

令u=i，v=j，则

与已知矛盾，故

为奇素数。反之，若

则

为奇合数。

定理2得证。

定理3 若给定正整数n（n≥4），则不等式组

中，i系数为奇合数的不等式的正整数解均包含在i系数为奇素数的不等式的正整数解之中。

证明 在

中，当2k+1为奇素数时，不必讨论；当2k+1为奇合数时，根据算术基本定理，必有

即

令2s+1为2k+1的最小素因数，并将(3)代入(2)得

令

则(4)式转化为

定理3得证。

3 素数分布的一种新筛法

令

其中n,i,j均为正整数，可得不超过N的所有素数的筛法步骤如下：

（1）考虑到 aij= aji，不妨设j≤i。依据且2j+1为素数求出全部的aij（i,j为满足条件的正整数）。

若

即

则此过程结束。然后计算

此时

是不超过N的全体奇合数。

（2）按从小到大的顺序列出不超过N的奇数序列

1，3，5，7，9，...，N。

（3）从上述序列中划去（1）中求出的每一个奇合数Aij及1，再添上2，即得不超过N的全部素数。

4 应用举例

作为上述筛法的应用，我们来求不超过N=199的全部素数。

（1）由 2n+ 1= 199知，n=99，此时j≤7。

j=1时， 2j+1=3为素数， ai1= 3i +1，由

知，1≤i≤32，可算出

ai1=4，7，10，13，16，19，22，25，28，31，34，37，40，43，46，49，52，55，58，61，64，67，70，73，76，79，82，85，88，91，94，97。

j =2时， 2j+1=5为素数， ai2= 5i +2，由

知，2≤i≤19，可算出

ai2=12，17，22，27，32，37，42，47，52，57，62，67，72，77，82，87，92，97。

j=3时， 2j+1= 7为素数， ai3= 7 i+3，由

知，3≤i≤13，可算出

ai3=24，31，38，45，52，59，66，73，80，87，94。

j =4时， 2j+ 1= 9为合数，不必考虑。

j =5时， 2j+1= 11为素数， ai5= 11i +5，由

知，5≤i≤8，可算出 ai5=60，71，82，93。

j =6时， 2j+1= 13为素数， ai6= 13i +6，由

知，6≤i≤7，可算出 ai6=84，97。

j =7时， 2j+ 1= 15为合数，不必考虑。

综上，aij等于

4，7，10，12，13，16，17，19，22，24，25，27，28，31，32，34，37，38，40，42，43，45，46，47，49，52， 55，57，58，59，60，61，62，64，66，67，70，71，72，73，76，77，79，80，82，84，85，87，88，91，92，93，94，97。

此时，Aij等于

9，15，21，25，27，33，35，39，45，49，51，55，57，63，65，69，75，77，81，85，87，91，93，95，99，105，111，115，117，119，121，123，125，129，133，135，141，143，145，147，153，155，159，161，165，169，171，175，177，183，185，187，189，195。

（2）列出不超过199的奇数序列

1，3，5，7，9，...，197，199.

（3）从上述序列中划去1）中求出的每一个奇合数Aij及1，再添上2，即得不超过199的全部素数为：

2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，101，103，107，109，113，127，131，137，139，149，151，157，163，167，173，179，181，191，193，197，199。

[1] 王元.谈谈素数[M].上海：上海教育出版社,1978.

[2] 左宗明.世界数学名题选讲[M].上海：上海科学技术出版社,1990.

[3] 华罗庚.数论导引[M].北京：科学出版社,1979.

[4] 陈景润.初等数论(I)[M].北京：科学出版社,1978.

[5] 陈景润.初等数论(II)[M].北京：科学出版社,1980.

[6] 王元.论哥德巴赫猜想[M].山东：山东教育出版社,1999.

[7] 潘承洞,潘承彪.哥德巴赫猜想[M].北京：科学出版社, 1981.

[8] 陈景润.大偶数表为一个素数及一个不超过二个素数的乘积之和[J].科学通报,1966,17：385-386

[9] 侯绍胜,王顺庆.奇合数的分解公式、素数分布及筛法[J].西北民族学院学报(自然科学版),2002,23(2)：1-6.

（责任编辑、校对：赵光峰）

A New Sieving Method for Seeking Prime Number Distribution

GUAN Xun-gui

(Mathematics & Physics of Taizhou Normal College, Taizhou 225300, China)

The composing law of odd integer numbers and odd prime numbers were revealed in the paper by giving the sieving equation of odd integer numbers. On the basis of these, a new simple sieving method for seeking prime number distribution was also put out.

odd integer; odd prime number; sieving equation; sieving method

2011-06-08

管训贵（1963-），男，江苏兴化人，泰州师范高等专科学校副教授，研究方向为基础数论。

O156.4

A

1009-9115(2011)05-0012-03