《挑战程序设计竞赛-求素数算法.ppt》由会员分享，可在线阅读，更多相关《挑战程序设计竞赛-求素数算法.ppt（14页珍藏版）》请在装配图网上搜索。
1、,挑战程序设计竞赛-求素数算法,素数（prime number） ，又称质数，指在大于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都不能被整除，则说明该数是素数。 根据以上思路，可编写以下的试除法函数：,试除法判断是否为素数的函数: int is_prime(int n) int i; if (n=1) return 0; /n不是素数，返回零 for(i=2; i=n; i+) if( n%i=0 ) return 0; /判断n能否被i整除 return 1; 其实，可以对素数的定义进行进一步的分析。要判断数n是否为素数，不需要用n一直除到n-1才能确认，而只需要除到n 而就可以了。例如，n=15，则能被15
4、整除的除数有1、3、5，对于除数5就不用判断，因为n被3整除时其商就是5，也就表示n能被5整除了。,改进后的是否为素数的函数: int is_prime(int n) int i; if (n=1) return 0; /n不是素数，返回零 for(i=2; i*i=n; i+) /for(int i = 2; i = sqrt(n); +i) if( n%i=0 ) return 0; /判断n能否被i整除 return 1; 改进后的程序中，在for循环中以i*i既i的平方与n值进行比较，就可以显著地减少循环的次数，提高验证的效率。 这里用了 i*i = n 来代替 sqrt(n)，可以避
5、免调用函数sqrt()，其消耗时间较多，特别是在大量数据测试的时候消耗很明显。,求出1000以内的所有素数: #include int is_prime(int n) for(int i=2;i*i=n;i+) if(n%i=0) return 0; return 1; int main() int i, n=1000, num = 0; for(i=2; i=n; i+) if(is_prime(i) printf(%3d ,i); return 0; ,在上面的代码中，通过is_prime()函数来验证指定区间(21000)中的每一个数是否为素数，而is_prime()函数中又通过循环进行
6、验证。这种双循环会导致程序执行效率不高。 试除法求解n以内素数的算法。复杂度是o(n*sqrt(n)，如果n很小的话，这种算法不会耗时很多。但是当n很大的时候，比如n=10000000时，n*sqrt(n)30000000000,数量级相当大。在一般的电脑上它不是一秒钟跑不出结果，它是好几分钟都跑不出结果的。 这时可考虑采用另一种寻找素数的算法：著名的筛法(Eratosthenes)求素数方法。,二、 筛法 Eratoslhenes算法假设有一个筛子，用来存放2100之间的所有数。 由于偶数都能被2整数，因此偶数都不是素数(2除外)，则将这些数筛去，得到如图-A所示的数据(设置了背景色的数字将
7、被筛去) 接着再将3的倍数筛去，得到如图-B所示结果。 接下来继续将5的倍数筛去，得到图-C所示结果。 最后再将7的倍数筛去，得到如图-D所示结果，即可得到100以内的所有素数。 原理很简单，就是当i是素数的时候，i的所有的倍数必然是合数。如果i已经被判断不是素数了，那么再找到i后面的素数来把这个素数的倍数筛掉。 下面用图来演示如何用这种方法求100以内的素数。,图-A 将2的倍数筛去 图-B 将3的倍数筛去 图-C 将5的倍数筛去 图-D 将7的倍数筛去,从前面的图示中可看到，在使用Eratosthenes算法进行筛选时，只需要执行4次筛选就完成了100以内的素数的筛选，效率非常高。如果要筛
8、选的数据范围更大，由于只需要选择已经筛选过的素数对后面的数进行筛选，因此可快速筛选出后面的素数。Eratosthenes算法比试除法的效率要高得多。 根据筛法所示的过程编写相应的程序，具体代码如下：,#include #define MAX 1000000 bool primeMAX; int main() int i,j,num=0; for (i=2;iMAX;i+) primei=true; for (i=2;iMAX;i+) if(primei) for(j=i+i;jMAX;j+=i) primej=false; for(i=2;iMAX;i+) if(primei=true) nu
9、m+; printf(%8d,i); printf(n Total=%d ,num); return 0； ,通过上面的筛法实现可以看出，用筛法直接判断素数是很有限的，筛法受内存的限制，要判断n是否为素数，需要开大小为n的bool数组。当n很大的时候，显然是不可取的。所以我们可以折中以上两种算法，将试除法和筛法结合在一起。 再深入理解，你确实会发现一个本质问题。从2到n 中，存在很多不必要的判断，比如，n不能被2整除的话，n必然不能被4整除，必然不能被2的倍数整除。所以，我们再结合筛选法，优化处理小于n 的所有素数。这样在大量测试数据的时候，效率就提高很多了。,void prime(int n) memset(isprime, 0, sizeof isprime); memset(p, 0, sizeof p); np = 0; for (int i = 2; i = n; i+) if (!isprimei) pnp+ = i; for (int j = 0; j np ,
挑战程序设计竞赛-求素数算法.ppt
