素數分布的一種新篩法

管訓貴

（泰州師范高等?？茖W校 數理系，江蘇泰州 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-），男，江蘇興化人，泰州師范高等?？茖W校副教授，研究方向為基礎數論。

O156.4

A

1009-9115(2011)05-0012-03