潘悅晨，張雷

（1.運城學院生命科學系,運城 044000；2.運城學院公共計算機教學部，運城 044000）

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

潘悅晨1，張雷2

（1.運城學院生命科學系,運城 044000；2.運城學院公共計算機教學部，運城 044000）

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

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

0 引言

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

在C語言程序設計課程中，程序的三種基本結構是需要掌握的重點內(nèi)容，而在這三種基本結構中，循環(huán)結構則是其中的難點。如果對循環(huán)結構的理解不透徹，不僅會影響學生對循環(huán)結構的使用，還會影響后續(xù)內(nèi)容的學習，例如數(shù)組的基本操作，因為數(shù)組的輸入輸出、排序、插入、刪除等操作都會用到循環(huán)結構。因此，對素數(shù)問題的理解程度往往成為檢驗一個學生對循環(huá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ù)進行判斷。在此期間，一旦有一個數(shù)能被n整除，則可以判定n不是素數(shù)。在此情況下，不需要再對其余的數(shù)進行判斷，則應立即結束循環(huán)，該功能可用break語句實現(xiàn)。如果從2到n-1之間的每個數(shù)都不能被n整除，則n為素數(shù)。根據(jù)以上分析，程序設計為：

2 運行效率改進

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

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

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

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

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

4 結語

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

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

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

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

[4]梁志劍.C語言程序設計課程考試模式改革實踐與研究[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-），男，江蘇南通人，學生

2017-01-10

2017-04-02

運城學院院級項目（No.JG201628）、運城學院院級項目（No.JG201629）

張雷（1980-），男，山西臨猗人，研究方向為機器學習、圖形圖像處理