浅析中学生求素数的算法

摘 要：学习计算机编程是培养一种思维方式——计算思维，也是一种思维体操，计算机编程将有助于开发青少年的学习潜能，提高中小学生的逻辑推理能力和解决问题的能力。信息学奥赛为中小学编程爱好者提供了一个很好的施展才华的舞台。素数算法是信息学竞赛和程序设计竞赛中常涉及的数论知识，探讨的是中学生求素数的常规算法问题。

关键词：素数；算法；信息学竞赛

全国青少年信息学奥林匹克竞赛（简称NOIP）是中学生五大学科（数学、物理、生物、化学、信息学）联赛之一，是一个能够激发青少年创新性思维和高超程序设计技巧的重要平台，越来越受到中学生编程爱好者的青睐。素数的算法是信息学竞赛和程序设计竞赛中常涉及的数论知识，在这里我们一起来探讨一下素数算法的问题。

一、判断一个数是否为素数

（1）根据定义求解：质数表的质数又称素数。指整数在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。依据定义用C++程序求解代码如下：

#include

using namespace std；

int main（ ）{

int n，i；

bool f=true；//假定n是符合条件的素数。

cin>>n；

for（i=2；i

if（f）cout<

else cout<

return 0；}

（2）算法是解决问题的步骤与方法，不同的方法必然导致不同的解题效果和程序运行效率。显然，依据定义进行判断，当n的值比较大时，以上程序进行循环判断的次数比较大，时间复杂度为O（n），需寻求方法对程序进行优化。

初步优化：利用break语句对不是素数的n值进行循环中断。即将程序稍加修改：

for（i=2；i

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

再优化：利用数学知识分析，我们不难知道，一个合数的最大因数不会超越[sqrt（n），n]区间，也就是较小的因素在[1，sqrt（n）]中，排除1，这程序可以修改如下：

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

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

二、求不大于n的所有素数，并记录素数的个数

方法一：综合以上探讨的内容，可以将本问题的主要程序代码设计如下。

int main（ ）{

int n，i，j，num=0；

cin>>n；

for（i=2；i<=n；i++）{//以下是对每个n的值进行判断及个数进行累计。

bool f=true；

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

if（f） {cout<

cout<

printf（“n里含有%d个素数＼n”，num）；//显然这里用printf语句输出更方便些。

return 0；}

三、歌尔巴的猜想

大于4的所有偶数均可以分解为两个素数之和。设符合条件的偶数为n，如果结论成立，其中较小的素数肯定不大于n/2。其实本题不用设bool变量也可以把程序设计出来。

int main（ ）{

int n，x，y，i；//设n可以分解为x和y的和

cin>>n；

for（x=3；x<=n/2；x+=2） {//枚举第一加数x

for（i=2；i<=sqrt（x）；i++）//判斷x是否为素数

if（x%i==0） break；//如何x被i整除，x为非素数，退出本轮循环。

if（i>sqrt（x）） y=n-x；//用同样的方法判断另外一个加数

else break；

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

if（y%i==0）break；

if（i>sqrt（y））cout<

}

return 0；}

运行结果如下：

18

18=5+13

你也可以设计一个子程序，让程序变得更简洁，不妨试试吧。

总之，青少年中学生学习计算机编程需要遵循循序渐进的原则，由浅入深，由简到繁，从已有的知识与经验入手，多思考、多实践。解决同类问题时，要逐步追求难度的深入、算法的创新，并在实践中检验自己设计的算法，用锲而不舍的精神思考算法的改进方法，从而提高自己的编程能力、实践能力和创新能力。

作者简介：柯贤根（1977—），湖北阳新人，阳新县第一中学信息技术教师，信息学奥赛辅导教练，华中师范大学教育硕士，研究方向为信息技术在教育中的应用。