淺析中學生求素數的算法

摘 要：學習計算機編程是培養一種思維方式——計算思維，也是一種思維體操，計算機編程將有助于開發青少年的學習潛能，提高中小學生的邏輯推理能力和解決問題的能力。信息學奧賽為中小學編程愛好者提供了一個很好的施展才華的舞臺。素數算法是信息學競賽和程序設計競賽中常涉及的數論知識，探討的是中學生求素數的常規算法問題。

關鍵詞：素數；算法；信息學競賽

全國青少年信息學奧林匹克競賽（簡稱NOIP）是中學生五大學科（數學、物理、生物、化學、信息學）聯賽之一，是一個能夠激發青少年創新性思維和高超程序設計技巧的重要平臺，越來越受到中學生編程愛好者的青睞。素數的算法是信息學競賽和程序設計競賽中常涉及的數論知識，在這里我們一起來探討一下素數算法的問題。

一、判斷一個數是否為素數

（1）根據定義求解：質數表的質數又稱素數。指整數在一個大于1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數。依據定義用C++程序求解代碼如下：

#include

using namespace std；

int main（ ）{

int n，i；

bool f=true；//假定n是符合條件的素數。

cin>>n；

for（i=2；i

if（f）cout<

else cout<

return 0；}

（2）算法是解決問題的步驟與方法，不同的方法必然導致不同的解題效果和程序運行效率。顯然，依據定義進行判斷，當n的值比較大時，以上程序進行循環判斷的次數比較大，時間復雜度為O（n），需尋求方法對程序進行優化。

初步優化：利用break語句對不是素數的n值進行循環中斷。即將程序稍加修改：

for（i=2；i

if（n%i==0） {f=false；break；}

再優化：利用數學知識分析，我們不難知道，一個合數的最大因數不會超越[sqrt（n），n]區間，也就是較小的因素在[1，sqrt（n）]中，排除1，這程序可以修改如下：

for（i=2；i< =sqrt（n）；i++）//用sqrt（n）后，記得在文件頭加#include。

if（n%i==0）{f=false；break；}

二、求不大于n的所有素數，并記錄素數的個數

方法一：綜合以上探討的內容，可以將本問題的主要程序代碼設計如下。

int main（ ）{

int n，i，j，num=0；

cin>>n；

for（i=2；i<=n；i++）{//以下是對每個n的值進行判斷及個數進行累計。

bool f=true；

for（j=2；j< =sqrt（i）； j++） if（i%j==0） { f=false； break； }

if（f） {cout<

cout<

printf（“n里含有%d個素數＼n”，num）；//顯然這里用printf語句輸出更方便些。

return 0；}

三、歌爾巴的猜想

大于4的所有偶數均可以分解為兩個素數之和。設符合條件的偶數為n，如果結論成立，其中較小的素數肯定不大于n/2。其實本題不用設bool變量也可以把程序設計出來。

int main（ ）{

int n，x，y，i；//設n可以分解為x和y的和

cin>>n；

for（x=3；x<=n/2；x+=2） {//枚舉第一加數x

for（i=2；i<=sqrt（x）；i++）//判斷x是否為素數

if（x%i==0） break；//如何x被i整除，x為非素數，退出本輪循環。

if（i>sqrt（x）） y=n-x；//用同樣的方法判斷另外一個加數

else break；

for（i=2；i<=sqrt（y）；i++）

if（y%i==0）break；

if（i>sqrt（y））cout<

}

return 0；}

運行結果如下：

18

18=5+13

你也可以設計一個子程序，讓程序變得更簡潔，不妨試試吧。

總之，青少年中學生學習計算機編程需要遵循循序漸進的原則，由淺入深，由簡到繁，從已有的知識與經驗入手，多思考、多實踐。解決同類問題時，要逐步追求難度的深入、算法的創新，并在實踐中檢驗自己設計的算法，用鍥而不舍的精神思考算法的改進方法，從而提高自己的編程能力、實踐能力和創新能力。

作者簡介：柯賢根（1977—），湖北陽新人，陽新縣第一中學信息技術教師，信息學奧賽輔導教練，華中師范大學教育碩士，研究方向為信息技術在教育中的應用。