淺析中學(xué)生求素?cái)?shù)的算法

摘 要：學(xué)習(xí)計(jì)算機(jī)編程是培養(yǎng)一種思維方式——計(jì)算思維，也是一種思維體操，計(jì)算機(jī)編程將有助于開發(fā)青少年的學(xué)習(xí)潛能，提高中小學(xué)生的邏輯推理能力和解決問題的能力。信息學(xué)奧賽為中小學(xué)編程愛好者提供了一個(gè)很好的施展才華的舞臺(tái)。素?cái)?shù)算法是信息學(xué)競(jìng)賽和程序設(shè)計(jì)競(jìng)賽中常涉及的數(shù)論知識(shí)，探討的是中學(xué)生求素?cái)?shù)的常規(guī)算法問題。

關(guān)鍵詞：素?cái)?shù)；算法；信息學(xué)競(jìng)賽

全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽（簡(jiǎn)稱NOIP）是中學(xué)生五大學(xué)科（數(shù)學(xué)、物理、生物、化學(xué)、信息學(xué)）聯(lián)賽之一，是一個(gè)能夠激發(fā)青少年創(chuàng)新性思維和高超程序設(shè)計(jì)技巧的重要平臺(tái)，越來越受到中學(xué)生編程愛好者的青睞。素?cái)?shù)的算法是信息學(xué)競(jìng)賽和程序設(shè)計(jì)競(jìng)賽中常涉及的數(shù)論知識(shí)，在這里我們一起來探討一下素?cái)?shù)算法的問題。

一、判斷一個(gè)數(shù)是否為素?cái)?shù)

（1）根據(jù)定義求解：質(zhì)數(shù)表的質(zhì)數(shù)又稱素?cái)?shù)。指整數(shù)在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，沒法被其他自然數(shù)整除的數(shù)。依據(jù)定義用C++程序求解代碼如下：

#include

using namespace std；

int main（ ）{

int n，i；

bool f=true；//假定n是符合條件的素?cái)?shù)。

cin>>n；

for（i=2；i

if（f）cout<

else cout<

return 0；}

（2）算法是解決問題的步驟與方法，不同的方法必然導(dǎo)致不同的解題效果和程序運(yùn)行效率。顯然，依據(jù)定義進(jìn)行判斷，當(dāng)n的值比較大時(shí)，以上程序進(jìn)行循環(huán)判斷的次數(shù)比較大，時(shí)間復(fù)雜度為O（n），需尋求方法對(duì)程序進(jìn)行優(yōu)化。

初步優(yōu)化：利用break語句對(duì)不是素?cái)?shù)的n值進(jìn)行循環(huán)中斷。即將程序稍加修改：

for（i=2；i

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

再優(yōu)化：利用數(shù)學(xué)知識(shí)分析，我們不難知道，一個(gè)合數(shù)的最大因數(shù)不會(huì)超越[sqrt（n），n]區(qū)間，也就是較小的因素在[1，sqrt（n）]中，排除1，這程序可以修改如下：

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

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

二、求不大于n的所有素?cái)?shù)，并記錄素?cái)?shù)的個(gè)數(shù)

方法一：綜合以上探討的內(nèi)容，可以將本問題的主要程序代碼設(shè)計(jì)如下。

int main（ ）{

int n，i，j，num=0；

cin>>n；

for（i=2；i<=n；i++）{//以下是對(duì)每個(gè)n的值進(jìn)行判斷及個(gè)數(shù)進(jìn)行累計(jì)。

bool f=true；

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

if（f） {cout<

cout<

printf（“n里含有%d個(gè)素?cái)?shù)＼n”，num）；//顯然這里用printf語句輸出更方便些。

return 0；}

三、歌爾巴的猜想

大于4的所有偶數(shù)均可以分解為兩個(gè)素?cái)?shù)之和。設(shè)符合條件的偶數(shù)為n，如果結(jié)論成立，其中較小的素?cái)?shù)肯定不大于n/2。其實(shí)本題不用設(shè)bool變量也可以把程序設(shè)計(jì)出來。

int main（ ）{

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

cin>>n；

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

for（i=2；i<=sqrt（x）；i++）//判斷x是否為素?cái)?shù)

if（x%i==0） break；//如何x被i整除，x為非素?cái)?shù)，退出本輪循環(huán)。

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

else break；

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

if（y%i==0）break；

if（i>sqrt（y））cout<

}

return 0；}

運(yùn)行結(jié)果如下：

18

18=5+13

你也可以設(shè)計(jì)一個(gè)子程序，讓程序變得更簡(jiǎn)潔，不妨試試吧。

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

作者簡(jiǎn)介：柯賢根（1977—），湖北陽新人，陽新縣第一中學(xué)信息技術(shù)教師，信息學(xué)奧賽輔導(dǎo)教練，華中師范大學(xué)教育碩士，研究方向?yàn)樾畔⒓夹g(shù)在教育中的應(yīng)用。