浅析中学生求素数的算法

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

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

全国青少年信息学奥林匹克竞赛（简称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，这程序可以修改如下：