挑战程序设计竞赛-求素数算法

《挑战程序设计竞赛-求素数算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、挑战程序设计竞赛-求素数算法素数（primenumber），又称质数，指在大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着非常重要的地位。最小的素数是2，也是素数中唯一的偶数；其他素数都是奇数。素数有无限多个，所以不存在最大的素数。围绕著素数存在很多问题、猜想和定理。著名的有“孪生素数猜想”和“哥德巴赫猜想”。关于素数的算法是信息学竞赛和程序设计竞赛中经常出现的基础算法，虽然题目各不相同，但都要涉及验证一个自然数是否为素数的问题。下面探讨寻找

2、一定范围内素数的几个算法。根据以上思路，可编写以下的试除法函豹：其实，可以对素数的定义进行进一步的分析。要判断数n是否为素数，不需要用n一直除到n-1才能确认，而只需要除到√n而就可以了。例如，n=15，则能被15整除的除数有1、3、5，对于除数5就不用判断，因为n被3整除时其商就是5，也就表示n能被5整除了。验证一个自然数是否为素数，这个问题早在中世纪就引起人们的注意，当时人们还在寻找一个公式可以一劳永逸地解决求素数的问题，直到高斯提出了素数产生的不确定性后，人们才认识到没有一个公式可以简单确认素数，从而人们才转去寻找各种验证素数的方法。一、试除法试除法是根据素数

3、的定义得出的一种方法，用需要验证的数n逐个除以从2开始至n-1中的所有数，若能被某一个数整除，表示有一个因数，说明数n不是素数：若直到n-1都不能被整除，则说明该数是素数。根据以上思路，可编写以下的试除法函数：试除法判断是否为素数的函数:intis_prime(intn){inti;if(n<=1)return0;//n不是素数，返回零for(i=2;i<=n;i++){if(n%i==0)return0;//判断n能否被i整除}return1;}其实，可以对素数的定义进行进一步的分析。要判断数n是否为素数，不需要用n一直除到n-1才能确认，而只需要除到√n而就可以

4、了。例如，n=15，则能被15整除的除数有1、3、5，对于除数5就不用判断，因为n被3整除时其商就是5，也就表示n能被5整除了。改进后的是否为素数的函数:intis_prime(intn){inti;if(n<=1)return0;//n不是素数，返回零for(i=2;i*i<=n;i++)//for(inti=2;i<=sqrt(n);++i){if(n%i==0)return0;//判断n能否被i整除}return1;}改进后的程序中，在for循环中以i*i既i的平方与n值进行比较，就可以显著地减少循环的次数，提高验证的效率。这里用了i*i<=n来代替sqrt(

5、n)，可以避免调用函数sqrt()，其消耗时间较多，特别是在大量数据测试的时候消耗很明显。求出1000以内的所有素数:#includeintis_prime(intn){for(inti=2;i*i<=n;i++)if(n%i==0)return0;return1;}intmain(){inti,n=1000,num=0;for(i=2;i<=n;i++){if(is_prime(i))printf("%3d",i);}return0;}在上面的代码中，通过is_prime()函数来验证指定区间(2～1000)中的每一个数是否为素数，而is_prim

6、e()函数中又通过循环进行验证。这种双循环会导致程序执行效率不高。试除法求解n以内素数的算法。复杂度是o(n*sqrt(n))，如果n很小的话，这种算法不会耗时很多。但是当n很大的时候，比如n=10000000时，n*sqrt(n)>30000000000,数量级相当大。在一般的电脑上它不是一秒钟跑不出结果，它是好几分钟都跑不出结果的。这时可考虑采用另一种寻找素数的算法：著名的筛法(Eratosthenes)求素数方法。二、筛法Eratoslhenes算法假设有一个筛子，用来存放2~100之间的所有数。由于偶数都能被2整数，因此偶数都不是素数(2除外)，则将这些数筛

7、去，得到如图-A所示的数据(设置了背景色的数字将被筛去)接着再将3的倍数筛去，得到如图-B所示结果。接下来继续将5的倍数筛去，得到图-C所示结果。最后再将7的倍数筛去，得到如图-D所示结果，即可得到100以内的所有素数。原理很简单，就是当i是素数的时候，i的所有的倍数必然是合数。如果i已经被判断不是素数了，那么再找到i后面的素数来把这个素数的倍数筛掉。下面用图来演示如何用这种方法求100以内的素数。图-A将2的倍数筛去图-B将3的倍数筛去图-C将5的倍数筛去图-D将7的倍数筛去从前面的图示中可看到，在使用Eratosthenes算法进行筛选时，只需要执行4次筛选