C語言程序設(shè)計中的素數(shù)問題

潘悅晨，張雷

（1.運(yùn)城學(xué)院生命科學(xué)系,運(yùn)城 044000；2.運(yùn)城學(xué)院公共計算機(jī)教學(xué)部，運(yùn)城 044000）

C語言程序設(shè)計中的素數(shù)問題

潘悅晨1，張雷2

（1.運(yùn)城學(xué)院生命科學(xué)系,運(yùn)城 044000；2.運(yùn)城學(xué)院公共計算機(jī)教學(xué)部，運(yùn)城 044000）

C語言程序設(shè)計的主要目標(biāo)是培養(yǎng)學(xué)生的算法思維，提高學(xué)生利用所學(xué)知識分析問題和解決問題的能力。通過對素數(shù)問題的分析、程序?qū)崿F(xiàn)，以及在運(yùn)行效率和循環(huán)終止條件方面進(jìn)行的改進(jìn)，不僅可以深刻地理解循環(huán)結(jié)構(gòu)的基本執(zhí)行過程，而且可以激發(fā)學(xué)習(xí)興趣，提高獨(dú)立分析問題和解決問題的能力。

C語言；程序設(shè)計；素數(shù)

0 引言

目前，由于經(jīng)濟(jì)的快速發(fā)展以及社會需求的不斷變化，地方普通高等學(xué)校積極探索轉(zhuǎn)型發(fā)展，提出建設(shè)應(yīng)用型大學(xué)的新目標(biāo)[1]，研究應(yīng)用型人才培養(yǎng)的方案、模式、體系，開展教學(xué)方法改革[2]。在以培養(yǎng)應(yīng)用型人才為主要目標(biāo)的背景下，各高等院校為本科生開設(shè)了應(yīng)用型較強(qiáng)的專業(yè)基礎(chǔ)課，目的是培養(yǎng)學(xué)生的動手能力，提高學(xué)生獨(dú)立分析問題和解決問題的能力，使學(xué)生能夠?qū)⑺鶎W(xué)知識應(yīng)用于實(shí)際，解決具體問題[3]。因此，在程序設(shè)計方面，各高校都為學(xué)生開設(shè)了C語言程序設(shè)計，目的就是培養(yǎng)學(xué)生的算法思維，提高動手能力[4]。

在C語言程序設(shè)計課程中，程序的三種基本結(jié)構(gòu)是需要掌握的重點(diǎn)內(nèi)容，而在這三種基本結(jié)構(gòu)中，循環(huán)結(jié)構(gòu)則是其中的難點(diǎn)。如果對循環(huán)結(jié)構(gòu)的理解不透徹，不僅會影響學(xué)生對循環(huán)結(jié)構(gòu)的使用，還會影響后續(xù)內(nèi)容的學(xué)習(xí)，例如數(shù)組的基本操作，因?yàn)閿?shù)組的輸入輸出、排序、插入、刪除等操作都會用到循環(huán)結(jié)構(gòu)。因此，對素數(shù)問題的理解程度往往成為檢驗(yàn)一個學(xué)生對循環(huán)結(jié)構(gòu)掌握程度的衡量標(biāo)準(zhǔn)。

1 素數(shù)問題

素數(shù)的定義為：在大于1的自然數(shù)中，除了1和它本身以外不再有其他因子的數(shù)稱為素數(shù)。因此，首先可以根據(jù)素數(shù)的定義判斷一個自然數(shù)是否是素數(shù)。

算法思想：對于一個大于1的自然數(shù)n，依次判斷在[2，n-1]范圍內(nèi)的每個數(shù)是否能被n整除，如果該范圍內(nèi)只要有一個數(shù)能被n整除，則n不是素數(shù)，否則n是素數(shù)。

程序分析：判斷過程是一個循環(huán)過程，需要依次將從2到n-1之間的每個數(shù)進(jìn)行判斷。在此期間，一旦有一個數(shù)能被n整除，則可以判定n不是素數(shù)。在此情況下，不需要再對其余的數(shù)進(jìn)行判斷，則應(yīng)立即結(jié)束循環(huán)，該功能可用break語句實(shí)現(xiàn)。如果從2到n-1之間的每個數(shù)都不能被n整除，則n為素數(shù)。根據(jù)以上分析，程序設(shè)計為：

2 運(yùn)行效率改進(jìn)

根據(jù)素數(shù)的定義編寫的程序可以實(shí)現(xiàn)對素數(shù)的判斷，但可以從運(yùn)行效率的角度進(jìn)行改進(jìn)。根據(jù)數(shù)學(xué)上的相關(guān)證明可知，若一個自然數(shù)n在[2，sqrt（n）]范圍內(nèi)無因子，則該數(shù)為素數(shù)，否則不是素數(shù)。因此，在循環(huán)過程中只需將從2到sqrt（n）之間的自然數(shù)依次判斷即可，相對于范圍[2，N-1]可以在很大程度上減少循環(huán)次數(shù)，從而大幅度提高程序的運(yùn)行效率。改進(jìn)之后的程序如下所示：

3 循環(huán)終止條件改進(jìn)

素數(shù)問題的難點(diǎn)之一是，在利用循環(huán)結(jié)構(gòu)依次對[2，sqrt（n）]范圍內(nèi)每個自然數(shù)進(jìn)行判斷的過程中，一旦發(fā)現(xiàn)某個數(shù)能被n整除，則應(yīng)立即結(jié)束循環(huán)。最后，需要根據(jù)循環(huán)是否正常結(jié)束判斷n是否是素數(shù)。在上述程序中，變量從2循環(huán)到sqrt（n），如果循環(huán)正常結(jié)束，則k的值應(yīng)該大于sqrt（n）。如果循環(huán)是中途通過break語句結(jié)束，則k的值應(yīng)該小于等于sqrt（n），因此，在循環(huán)結(jié)束之后，通過比較k和sqrt（n）的值判斷n是否是素數(shù)。

但是對于上述循環(huán)結(jié)束條件的判斷，理解起來相對比較困難。因此，將上述程序進(jìn)行改進(jìn)，在程序中增加一個變量f，用該變量表示循環(huán)是否正常結(jié)束。改進(jìn)之后的程序如下所示：

從以上的程序可以看出，增加了變量f之后，對循環(huán)是否正常結(jié)束的判斷則變得簡單，非常容易理解。變量f的初始值設(shè)置為1，如果在循環(huán)結(jié)束之后，變量f的值仍然為1，則說明f=0語句沒有運(yùn)行，進(jìn)而說明n% k==0這個條件沒有成立過，因此意味著在[2，sqrt（n）]區(qū)間的每個自然數(shù)都不能被n整除，說明n是素數(shù)。反之，如果在循環(huán)結(jié)束之后，變量f的值變?yōu)?，則說明在循環(huán)過程中運(yùn)行了f=0語句，因此意味著在[2，sqrt（n）]區(qū)間有某個數(shù)可以被n整除，說明n不是素數(shù)。

4 結(jié)語

循環(huán)結(jié)構(gòu)是C語言程序設(shè)計中較難理解的內(nèi)容，很多學(xué)生對循環(huán)結(jié)構(gòu)的執(zhí)行過程理解不透徹，這對后續(xù)一維數(shù)組的使用會造成較大的障礙。通過對素數(shù)問題的理解分析以及對程序的改進(jìn)，不僅對循環(huán)結(jié)構(gòu)的基本執(zhí)行過程有了深刻的理解，而且可以舉一反三，根據(jù)改進(jìn)思路把自己的算法用具體的程序予以實(shí)現(xiàn)。從學(xué)生角度出發(fā)，不僅可以切身感受到C語言程序設(shè)計的實(shí)用性，更重要的是可以激發(fā)學(xué)生的學(xué)習(xí)興趣。下一步將對C語言程序設(shè)計中的回文串判斷問題進(jìn)行深入研究。

[1]薛玉香，王占仁.地方高校應(yīng)用型人才培養(yǎng)特色研究[J].高等工程教育研究，2016（1）:149-153.

[2]朱苗苗，常晉義，牛國鋒.基于應(yīng)用型人才培養(yǎng)的計算機(jī)基礎(chǔ)實(shí)驗(yàn)教學(xué)研究[J].計算機(jī)教育，2015（5）:81-83.

[3]田琳琳，劉斌，于紅,等.面向應(yīng)用型創(chuàng)新人才培養(yǎng)的程序設(shè)計語言實(shí)驗(yàn)教學(xué)[J].計算機(jī)教育，2016,255（3）:12-15.

[4]梁志劍.C語言程序設(shè)計課程考試模式改革實(shí)踐與研究[J].計算機(jī)教育,2016,258（6）:139-142.

The Problem of Prime in C Language Programming

PAN Yue-chen1，ZHANG Lei2
（1.Department of Life Sciences,Yuncheng University,Yuncheng 044000；2.Department of Public Computer Teaching,Yuncheng University,Yuncheng 044000）

The main goal of C language programming is to train students'algorithm thinking,and improve students'ability to analyze and solve problems.Through the analysis of prime problem,program implementation,as well as improvements in operating efficiency and cyclic termination conditions,students can not only deeply understand the basic implementation of the cycle structure,but also stimulate their interest in learning,and improve the ability to analyze and solve problems independently.

C Language;Programming;Prime

1007-1423（2017）10-0031-03

10.3969/j.issn.1007-1423.2017.10.008

潘悅晨（1996-），男，江蘇南通人，學(xué)生

2017-01-10

2017-04-02

運(yùn)城學(xué)院院級項目（No.JG201628）、運(yùn)城學(xué)院院級項目（No.JG201629）

張雷（1980-），男，山西臨猗人，研究方向?yàn)闄C(jī)器學(xué)習(xí)、圖形圖像處理