篩法在實際應用的探討

梁增勇

摘 要：

在研究質數的問題中常常運用到篩法計算質數的個數。本文介紹用更苛刻的篩除法求出質數對的可靠下限，同時用函數等數學分析的方法進行分析，即可解決這類性質的關鍵問題。

關鍵詞：集合；函數；篩法；整數對；數學分析

一、本文使用的數學符號的定義：

全體非負整數的集合通常簡稱非負整數集（或自然數集），記作N[1]。本文中

A表示[1，n]區間正整數的集合，即A ={1，2，3，…，n}， 集合A的元素個數記為card （A）；

A＼-p為含有p素因子倍數的子集， 即A＼-p ={1p，2p，3p， 4p， 5p，……}， A＼-＼{2，3＼}={2，3，4，6，8，9}，（n=10） ；

B＼-p 為集合A不含p素因子合數子集（除了2），例如B＼-2是奇數的子集， B＼-＼{2，3＼}={1，3，5，7}，（n=10）；

P表示素數的集合，p或p＼-m 表示素數，即P={2，3，5，7，11，13，……， p， ……，} 或 P = {p＼-1 ， p＼-2 ， p＼-3 ，…， p＼-m ，…}，

ф（n）為歐拉函數，ф′（n）、h（n）為非合數個數的下限函數。d（n）為質數對個數的下限函數。

容斥原理是在組合數學中應用頗為廣泛的一個工具，它常使用到容斥公式[2]。例如：

例1 設A是一個由整數組成的有限集合，d＼-1， d＼-2， …， d＼-m 是給定的正整數，再設A＼-d 表A中被正整數d整除的元素組成的子集，那么，A中不能被任一dj（1≤j≤m）整除的元素的個數等于

|A | -Σ1≤i≤m|Ad＼-i| + Σ1≤i≤j≤m|Ad＼-j∩ Ad＼-j |-… + （-1）＼+＼{m-1＼} | Ad＼-1∩ Ad＼-2∩…∩Ad＼-m|

由于取整運算十分是復雜， 僅可以在小范圍內計算。對于更大范圍的數據運算是無能為力的。下面我們介紹運用篩法、函數和數學分析解決這類性質的問題的幾個對策和方法。

1、質數個數的下限函數

引理1[2]. 若p為任一質數，A＼-p 為n個連續自然數中含質數p的所有倍數的集合，則

card（A＼-p）≤np]= [kn+rp]=k ≤np = k+rp，因為 （rp ≥0） ， 所以 card（A＼-p）≤np 。

定理1. 若p為任一質數，B＼-p 為n個連續自然數篩除去質數p的所有合數的集合，則

Card（B＼-p）≥n（1-1p ）。

證 由引理1得，card（A＼-p） ≤np ，則card（B＼-p）=n-card（A＼-p）≥n-np = n（1-1p

）。

引理2 （Euler函數）[3] 若 n含任意質數p＼-i、p＼-j、……p＼-k 之因子，則 ф（n）= n （1-np＼-i ） （1-np＼-j）…（1-np＼-k） （1）

定理2. 若2，3，…，p＼-i為質數，p＼-i≤（2）

證 由引理2 可知， 函數φ（n） 是當n為2×3×5×……×p＼-k 時可計算得之準確值，當n與上述整數有互素的情況，因函數ф（n）轉為ф′（n） ，由定理1可知每個因子（1-n22P＼-1 ） （ 1-2P＼-22P＼-i ）（3）

證 集合H的2n自然數可排成上、下兩行組成n個相同性質的對偶數對，并篩除所有含合數的對偶數對。根據定理2，僅篩除上行含合數的對偶數對，余下個數為 card（B＼-＼{2，3，…，P＼-＼{i+1＼}＼} ）≥ф′（n）= n （1-13）…（1-1P＼-i）

再考慮對帶奇合數對偶數重復篩除一次，即將括弧中1/p＼-i改為2/p＼-i，得到

card（B＼-＼{2，3，…，P＼-＼{i+1＼}＼}）≥d（n）= n（1-23）…（1-2P＼-i）

此即所謂重復篩除法，函數d（n）必然小于或等于非合性質元素對偶數對個數的實際值card（D）， 即

card（D） ≥d（n） = n2（ 1-2P＼-2） （ 1-2P＼-2 ）…（ 1-2P＼-i）

定理4 令N′為N之子集 ，card（N′）=2n ，2n≤p＼-m＼+2+1， 那么當

n2Πmi=2（1-2P＼-i）≥4（4）

成立，必定有一對或一對以上的同性質（例如相關質數）對偶數對存在。

證 已知N′的元素排列成n組同性質對偶數。由定理3可知，集合D已經不含任何的合數，d（n）為集合D元素個數的下限函數。 那么，當d（n） ≥ 4 （ 取保守一點） ），可組成至少兩對對偶數（可能有一對含數1）這樣，至少 有一對或一對以上對偶數對全是同性質整數存在。

定理5 令N′為N之子集 ，card（N′）=2n ，2n≤p＼-m＼+2+1， 則

（5）

證 對m使用數學歸納法[2]：1）當 m=6， n=170，d（n′）= [參考文獻]

[1] 同濟大學應用數學系主編 . 高等數學.[M]高等教育出版社，1978 ：1-23.

[2]潘承洞，潘承彪. 初等數論. [M]北京大學出版社， 2003：71-76.

[3]G.H.Hardy，E.M.Wright，An Introduction to the Theory of Numbers.[M].人民郵電出版社， 2007：52-53.

（作者單位：廣西婦幼保健院，廣西 南寧 530000）endprint