C語言程序設計中的素數問題

潘悅晨，張雷

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

C語言程序設計中的素數問題

潘悅晨1，張雷2

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

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

C語言；程序設計；素數

0 引言

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

在C語言程序設計課程中，程序的三種基本結構是需要掌握的重點內容，而在這三種基本結構中，循環結構則是其中的難點。如果對循環結構的理解不透徹，不僅會影響學生對循環結構的使用，還會影響后續內容的學習，例如數組的基本操作，因為數組的輸入輸出、排序、插入、刪除等操作都會用到循環結構。因此，對素數問題的理解程度往往成為檢驗一個學生對循環結構掌握程度的衡量標準。

1 素數問題

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

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

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

2 運行效率改進

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

3 循環終止條件改進

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

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

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

4 結語

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

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

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

[3]田琳琳，劉斌，于紅,等.面向應用型創新人才培養的程序設計語言實驗教學[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-），男，山西臨猗人，研究方向為機器學習、圖形圖像處理