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

挑战程序设计竞赛挑战程序设计竞赛- -求素数求素数算法算法 素数（prime number） ，又称质数，指在大于1的自 然数中，除了1和此整数自身外，无法被其他自然数整除的 数（也可定义为只有1和本身两个因数的数）。 比1大但不是素数的数称为合数。1和0既非素数也非合 数。素数在数论中有着非常重要的地位。 最小的素数是2，也是素数中唯一的偶数；其他素数都 是奇数。素数有无限多个，所以不存在最大的素数。 围绕著素数存在很多问题、猜想和定理。著名的有“孪 生素数猜想”和“哥德巴赫猜想”。 关于素数的算法是信息学竞赛和程序设计竞赛中经常出 现的基础算法，虽然题目各不相同，但都要涉及验证一个自 然数是否为素数的问题。下面探讨寻找一定范围内素数的几 个算法。 根据以上思路，可编写以下的试除法函豹： 其实，可以对素数的定义进行进一步的分析。要判断数 n是否为素数，不需要用n一直除到n-1才能确认，而只需要 除到n 而就可以了。例如，n=15，则能被15整除的除数有 1、3、5，对于除数5就不用判断，因为n被3整除时其商就 是5，也就表示n能被5整除了。 验证一个自然数是否为素数，这个问题早在中世纪就 引起人们的注意，当时人们还在寻找一个公式可以一劳永 逸地解决求素数的问题，直到高斯提出了素数产生的不确 定性后，人们才认识到没有一个公式可以简单确认素数， 从而人们才转去寻找各种验证素数的方法。 一、试除法 试除法是根据素数的定义得出的一种方法，用需要验证 的数n逐个除以从2开始至n-1中的所有数，若能被某一个数 整除，表示有一个因数，说明数n不是素数：若直到n-1都 不能被整除，则说明该数是素数。 根据以上思路，可编写以下的试除法函数： 试除法判断是否为素数的函数: int is_prime(int n) int i; if (n int is_prime(int n) for(int i=2;i*i30000000000,数量级 相当大。在一般的电脑上它不是一秒钟跑不出结果，它是好 几分钟都跑不出结果的。 这时可考虑采用另一种寻找素数的算法：著名的筛法 (Eratosthenes)求素数方法。 二、 筛法 Eratoslhenes算法假设有一个筛子，用来存放2100之 间的所有数。 由于偶数都能被2整数，因此偶数都不是素数(2除外)， 则将这些数筛去，得到如图-A所示的数据(设置了背景色的 数字将被筛去) 接着再将3的倍数筛去，得到如图-B所示结果。 接下来继续将5的倍数筛去，得到图-C所示结果。 最后再将7的倍数筛去，得到如图-D所示结果，即可得 到100以内的所有素数。 原理很简单，就是当i是素数的时候，i的所有的倍数必 然是合数。如果i已经被判断不是素数了，那么再找到i后面 的素数来把这个素数的倍数筛掉。 下面用图来演示如何用这种方法求100以内的素数。 图-A 将2的倍数筛去 图-B 将3的倍数筛去 图-C 将5的倍数筛去 图-D 将7的倍数筛去 从前面的图示中可看到，在使用Eratosthenes算法进行 筛选时，只需要执行4次筛选就完成了100以内的素数的筛 选，效率非常高。如果要筛选的数据范围更大，由于只需要 选择已经筛选过的素数对后面的数进行筛选，因此可快速筛 选出后面的素数。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) num+; 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 j+) isprimepj*i = 1; if