素數(shù)問題在C語言教學中的應用

黃昌軍　李音　柴榮軍

摘 要： 作為C語言的典型問題，素數(shù)問題可以在整個教學過程中反復出現(xiàn)。素數(shù)問題本身有一定的趣味性，同時反復處理同一問題可以在一定程度上降低學習難度。因此，在C語言的各教學環(huán)節(jié)有意識地使用素數(shù)問題舉例可望有效增強學習效果。

關鍵詞： C語言 素數(shù) 教學應用

素數(shù)在很多領域都有應用，例如作為公鑰密碼國際標準的RSA算法，就是基于兩個大素數(shù)的乘積實現(xiàn)的。素數(shù)問題在C語言中很重要，在算法、循環(huán)、數(shù)組、函數(shù)等章節(jié)均可出現(xiàn)，本文對素數(shù)問題在各章節(jié)的具體應用加以總結分析。

1.素數(shù)和算法描述

算法是計算機為求解特定問題而采取的方法和步驟，為加深學生對計算機算法的理解程度，將判斷素數(shù)的算法作為計算機算法的描述示例。

要判斷n是否素數(shù)，可以讓它除以2、除以3、……一直到除以n-1，只要有任一個能整除它就不是素數(shù)，反之如果不能整除就是素數(shù)，算法具體如下。

步驟1：從鍵盤上輸入n的值；

步驟2：2→i；

步驟3：n除以i，得到余數(shù)r，若r等于0，表示能夠整除，打印n“不是素數(shù)”，算法結束，否則執(zhí)行步驟4；

步驟4：i+1→i；

步驟5：如果i小于等于n-1轉步驟3，否則打印n“是素數(shù)”，算法結束。

2.素數(shù)和循環(huán)

循環(huán)是非常重要的一種基本結構，特點是在給定條件成立時多次重復執(zhí)行某個程序段，使用循環(huán)結構可以大幅度提高編程效率，將素數(shù)判斷程序作為循環(huán)結構的示例程序。

程序中的循環(huán)變量終值使用的是sqrt（n），與使用n-1或者n/2作為循環(huán)變量終值相比，循環(huán)執(zhí)行次數(shù)更少，因而效率更高。

3.素數(shù)和數(shù)組

數(shù)組部分可以使用篩法求某一范圍內的素數(shù)。篩法是另一種判斷素數(shù)的簡單算法，方法是先在紙上按順序寫下2～100，然后依次挖掉2的倍數(shù)、3的倍數(shù)、5的倍數(shù)……紙上最后剩下的就是100之內所有的素數(shù)。

4.素數(shù)和函數(shù)

函數(shù)屬于C語言中難度較高的部分，講授這部分時可以編寫一個判斷素數(shù)的函數(shù)，調用此函數(shù)驗證著名的哥德巴赫猜想。哥德巴赫猜想可以簡單描述為任一大于等于6的偶數(shù)都可以分解為兩個素數(shù)之和。以下程序對6～100之間的偶數(shù)進行哥德巴赫猜想的驗證。

由以上示例可見，素數(shù)問題可以在C語言整個教學過程中反復出現(xiàn)。對學生來說，素數(shù)問題本身有一定的趣味性，同時反復處理同一問題可以在一定程度上降低學習難度。因此，在C語言的各個教學環(huán)節(jié)有意識地使用素數(shù)問題舉例可望有效增強學習效果。

參考文獻：

[1]王文東，李竹林.C語言程序設計[M].西北大學出版社，2014.

基金項目：延安大學西安創(chuàng)新學院2014年度科學研究項目“MOOC課程平臺在計算機專業(yè)教學中的應用研究”（項目編號：14KY12）。