信息学竞赛中质数解法及优化.doc

信息学竞赛中质数解法及优化江西省信息学奥林匹克代表队领队、教练九江市第一中学 龚 禹作者简介：龚禹，1983年7月毕业于江西大学，从事计算机的相关工作二十余年，积累了丰富的实际工作经验，2002年9月开始投入信息学奥赛的教研工作，三年多来取得了丰硕的教学成果。他的弟子连续四年获得九江市信息学奥赛普及组第一名，2004年开始率初中生进军高中组，并连续两年获得九江市信息学奥赛提高组第一、二名。在全国信息学奥林匹克分区联赛（NOIP）与全国信息学奥林匹克竞赛（NOI）上也取得了不俗的成绩，2002年11月率初一学生夺的第八届NOIP普及组一等奖、江西赛区第一名；2004年11月率两名初中学生分夺第十届NOIP提高组一等奖、二等奖，分别入选第22届江西省信息学奥林匹克代表队与同步举办的夏令营队；2005年8月率初中生以248分的成绩夺的第22届全国信息学奥林匹克竞赛（NOI2005）同步夏令营铜奖（全国铜奖分数线为223分），创造了我省初中生在全国高中学科竞赛中获奖的记录。问题：求小于10000的所有质数。这是初学者常见的一道问题。首先，让我们回顾一下质数的定义：如果一个大于1的自然数，只能被1和它本身整除，那么这个自然数就是质数（素数）。一、枚举方法1. 简单枚举法显然，根据这个质数的定义，我们想到，要判断一个数是否为质数，只要判断所有大于1且小于它的自然数都不能被其整除就可以了。因此，我们得出了一种解这道题的方法，大体策略为：枚举所有小于10000的数，判断其是否为质数，若是质数则输出。这种方法我们称之为“枚举法”。但使用简单枚举法设计的程序运行的时间是漫长的，效率十分低下。仔细分析，可发现枚举的思路可分为两部分：枚举和判断。那么，我们能否从这两部分入手，对算法进行改进。2. 对枚举数字的改进首先是改进枚举，宗旨是尽量不要枚举那些显然不是质数的数。由于2是质数，那么根据质数的定义，4，6，8，都不会是质数。因此，我们得出了这样一个结论：所有大于2的偶数都不是质数。通过对枚举数字上的改进，使得速度提高了1倍，接着思考如何改进判断宗旨是尽量减少判断的量。3. 对枚举范围的改进如果一个数N不是质数，那么它必定可以表示成NAB，其中A、B为大于1的自然数，同时不妨设AB。那么，必然有A2N，由此得出：A，即N有不大于的非1的约数。反之，如果N没有不大于于的非1的约数，那么，N必然是质数。由此，我们可以对判断一个数是否是质数的范围由简单枚举的1N-1减少到。4. 用质因子枚举的方法要注意到我们刚才提到了有关N的约数，显然，如果N不是质数，那么必然有大于1小于N的一些约数，而这些约数中必然有质数这就是我们常说的一个数的质因子！也就是说，如果一个数没有小于它本身的质因子，那么这个数就是质数。于是，我们的判断又可以做这样的改进：利用数组按从小到大的顺序依次记录了质数。然后用小于的质数作为判别的基准即可。判断是否为质数的算法，至此已经有了很大的进步，程序也基本能在很短的时间内出解了。然而，是不是求质数只能用“枚举法”呢？研究过数学的同学可能会很快想到另一种著名的方法“筛选法”。二、筛选方法1. 简单筛选法回顾前面我们对判断是否为质数的算法所作的最后的改进：如果一个数没有小于它本身的质因子，那么这个数就是质数。不妨从另一个角度考虑，如果我们知道了一些质数，那么显然，这些质数的2倍，3倍，4倍都不会是质数，我们就可以将这些2倍，3倍，4倍的数字“筛”去，这就是解本题的另一种方法“筛选法”。大致步骤如下：（1）当前最大的质数X为2，可能为质数的集合S为3.10000。（2）将X的2倍，3倍，4倍数字从集合S中删去。（3）如果集合S为空，则结束；否则转到（4）。（4）当前最大质数X的值更新为当前集合S中的最小值，返回（2）。显然，每次从集合S中选取的最小值必定为质数，X的值逐渐增大，集合S逐渐减小。由于集合操作速度慢，且存储量有限，因此，在程序实现中，我们用ok : array2.10000 of boolean来代替集合S，okifalse表示i不是质数。对于“筛选法”的改进，主要也体现在两个方面枚举要筛选的质数和筛选的过程。2. 对要筛选的质数范围的改进假设要求的质数上限为N，那么显而易见，根据“枚举法”的一个结论，即一个数若不是质数，则必然含有小于的质因子。因此，“筛选法”所要枚举的质数仅仅限于的范围内，对于其他大于的质数，只需打印，无须进行“筛选”。事实上，本次改进的效果并不是特别明显，因为，大于的质数即使进行筛选，由于其本身数值大，所以在N范围内可被筛选的数并不是很多。3. 对筛选过程的改进我们注意到，所有质数，除2以外，都是奇数。换句话说，所有偶数，除2以外，都不是质数。应用这个性质，我们将2作为特例进行特殊处理后，每次用求得的一个质数（必然为奇数）进行筛选时，不要2倍，3倍，4倍的筛选了，只要3倍，5倍，7倍筛选即可（因为奇数偶数偶数）。如此，“筛选法”效率从理论上就提高了1倍！至此，“筛选法”已经被改进得非常优秀了。事实上，“枚举法”和“筛选法”的改进之外还有许多，但编程的复杂度也会随之不断上升！（在竞赛中，求质数仅仅可能是某道题目的一个部分，应用上面的方法就已经足够了）三、枚举法与筛选法的比较这样，我们求质数时就有了两种不同的方法：“枚举法”和“筛选法”。现在，让我们从理论上来比较它们的运行效率。“枚举法”对于每个数都要枚举所有小于该数平方根的质数来判断，并根据最后改进的程序运行，比较次数见下表。上限N1000100001000005000001000000判断次数180433756644439520901112927405比例11.813.416.4110112运行时间0.01s0.01s0.50s4.90s10.05s我们看到，随着N的增加，判断次数的增加将是非常惊人的。“筛选法”是对每个质数（奇数）计算其倍数来筛选。同样根据“筛选法”最后改进的程序运行，“筛选”次数即赋值false的次数，见下表。上限N1000100001000005000001000000判断次数457599571556391987811068比例10.4610.6010.7210.7810.81运行时间0.01s0.01s0.11s0.38s0.77s可见，“筛选法”的效率要大大优于“枚举法”。虽然在时间效率上，“筛选法”比“枚举法”要强许多，但是，大家可能会发现一个问题，即当上限N非常大的时候，“筛选法”的空间如何能够存储下（需要开一个1N的boolean数组）呢？其实这是可以解决的。在所开的boolean数组中，只需要记录下奇数的情况，这样原本需筛去数组中a值的3，5，7，倍，而新数组中a=2*i+1，其所处的位置位于i=(a-1) div 2，而其3倍的值则位于(3*aa) div 2iai，同理，其5，7，倍的值则分别位于2*ai，3*ai，的位置，这样可以节约一半的空间。四、一个例子【例】有一个正整数N（N可能达到120位），它是由若干个不大于65535的正整数相乘而得到的。请把这个数分解成素数因子（质因子）的乘积。输入：输入文件第一行为N的值。输出：（1）素数因子由小到大分行输出；（2）每一行输出一个素数因子和该素数因子的个数，用一个空格分开；（3）如果正整数N的分解中有一个以上的大于65535的素数，请按照（1）、（2）的要求输出分解中的小于65535的素数后，在下一行输出“Data Error”。【分析】求解一个数的质因子分解问题，其实用的方法就是数学中的试除法。首先用2去试除，若没有余数，则说明2是个该数的一个质因子，继续对除过的商进行同样的处理。如果余数不为0，则用下一个素数去试除，直至被除数等于1。在本题中，由于N的位数可能达到120位，因此需要用高精度除法，除数是2到65535之间的素数，为提高效率，先利用筛选法求解出2到65535之间的所有素数，依次