素數判定定理的延拓

唐 靜，趙美利

（滁州城市職業學院，安徽滁州 239000）

眾所周知，素數的判定問題一直是數論研究的中心問題之一，我們熟悉的歌德巴赫猜想、費爾瑪大定理[1]，他們與素數都有直接的關系，而素數的判定方法也在不斷改進。威爾遜[2]從同余角度給出了正整數P為質數的充分必要條件是，郝稚傳[3]給出若P是奇數，P是素數的充分必要條件為。從組合數的角度給出了奇數是素數的判定條件，開辟了一個新的途徑，在此基礎上如何找到更實用、更簡單、更一般的素數判斷新方法仍然是數論研究的熱點之一。王曉靜[4]給出了組合數被素數整除的一種判別法 。針對m，n數值較大時，吳躍生[5]給出組合數被素數整除的又一種判別法。蔣婭[6]總結了能被素數整除的組合數的形式若p為素數，則，但對一個正整數是否是素數，有沒有一個一般的方法均未作深入探討。以下對奇數是素數的一般方法進行簡單的探討，并基于C++語言給出程序實現。

1 預備知識

素數的定義：一個大于1的整數，除了1和他自身外，不能被任何一個數整除，則這個數稱為素數，否則就稱這個數是合數，2是最小的素數。

2 相關結論

該定理給出了更一般判定奇數是質數的充要條件，我們下面給出證明，并用JAVV語言給出程序設計及實現效果。要證明此結論，需要證明以下結論。

綜上所述引理4成立，由以上引理，我們容易得到定理的證明，下面我們來證明定理是正確的。

證明：“?”

所以定理得證。

下面我們驗證此定理的正確性和簡便化，比如，我們驗證7是否是素數，可以取n=3，r=2，k=2，得到能夠被7整除，所以7是素數。對于一個較大的正整數，如果用以前的方法和結論，會使判定步驟復雜化，比如用引理2的結論，我們將n和r的值代入，需要驗證和計算的步驟比較多，用此定理，當n確定下來后，由于r，k的任意性，我們可以通過r，k的取值，把問題簡單化，驗證條件簡單化，結果是正確的，此定理是對原來判定定理的延拓，更具有一般性。下面簡單給出此定理的算法設計及分析效果。

3 算法實現及優化

下面我們用JAVV語言來實現素數的判定，具體的程序)如下:

素數的判定問題是初等數論討論的核心問題之一，本文討論了一種較為簡單的判定方法，此方法較為簡單實用；素數的求解算法問題是計算機語言中的典型問題，出現在許多計算機課程教學中，關于這些問題的研究是永無止境的課題，需要我們進一步研究和探討。