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

信息学竞赛中质数解法及优化龚 禹问题：求小于10000的所有质数。这是初学者常见的一道问题。首先，让我们回顾一下质数的定义：如果一个大于1的自然数，只能被1和它本身整除，那么这个自然数就是质数（素数）。一、枚举方法1. 简单枚举法显然，根据这个质数的定义，我们想到，要判断一个数是否为质数，只要判断所有大于1且小于它的自然数都不能被其整除就可以了。因此，我们得出了一种解这道题的方法，大体策略为：枚举所有小于10000的数，判断其是否为质数，若是质数则输出。这种方法我们称之为“枚举法”。枚举法的不足之处在于程序运行的时间是漫长的，效率十分低下。仔细分析，枚举法解决问题的核心可它分为两部分：枚举和判断。那么，我们就分别从这两部分对算法进行改进。2. 对枚举数字的改进首先是改进枚举，宗旨是尽量不要枚举那些显然不是质数的数。由于2是质数，那么根据质数的定义，4，6，8，都不会是质数。因此，我们得出了这样一个结论：所有大于2的偶数都不是质数。那么，原方法按此改进的程序如下：var i, j : integer; ok : boolean;begin write(2:8); for i:=1 to 4999 do begin ok:=true; j:=2; repeat inc(j); if (2*i+1) mod j=0 then ok:=false; until (j=2*i) or (not ok); if ok then write(2*i+1:8); end;end.在枚举数字上如此改进，使得速度提高了1倍，接着再来看如何改进判断宗旨是尽量减少判断的量。3. 对枚举范围的改进如果一个数N不是质数，那么它必定可以表示成NAB，其中A、B为大于1的自然数，同时不妨设AB。那么，必然有A2N，由此得出：A，即N有不大于的非1的约数。反之，如果N没有不大于于的非1的约数，那么，N必然是质数。由此，我们可以对判断一个数是否是质数进行改进。程序如下var i, j : integer; ok : boolean;begin write(2:8); for i:=1 to 4999 do begin ok:=true; j:=2; repeat inc(j); if (2*i+1) mod j=0 then ok:=false; until (j=round(sqrt(2*i+1) or (not ok); if ok then write(2*i+1:8); end;end.4. 用质因子枚举的方法要注意到我们刚才提到了有关N的约数，显然，如果N不是质数，那么必然有大于1小于N的一些约数，而这些约数中必然有质数这就是我们常说的一个数的质因子！也就是说，如果一个数没有小于它本身的质因子，那么这个数就是质数。于是，我们的判断又可以做这样的改进：设Data数组按从小到大的顺序依次记录了质数。那么其程序如下：var i, j, len : integer; ok : boolean; data : array1.3000 of integer;begin write(2:8); len:=1; datalen:=2; for i:=1 to 4999 do begin ok:=true; j:=2; while (j=len) and (datajround(sqrt(2*i+1) and ok do begin if (2*i+1) mod dataj=0 then ok:=false; inc(j); end; if ok then begin write(2*i+1:8); inc(len); datalen:=2*i+1; end; end;end.注意：本例程序中判断质数的循环体存在一次都没有执行的可能性，因此使用while循环是比较好的，而上面其他的三个程序即可使用while循环，也可使用repeat循环。判断是否为质数的算法，至此已经有了很大的进步，程序也基本能在很短的时间内出解了。然而，是不是求质数只能用“枚举法”呢？研究过数学的同学可能会很快想到另一种著名的方法“筛选法”。二、筛选方法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不是质数。程序实现如下：var i, j : integer; ok : array1.10000 of boolean;begin fillchar(ok,sizeof(ok),true); for i:=2 to 10000 do if oki then begin write(i:8); j:=2*i; while (j=10000) do begin okj:=false; inc(j,i); end; end;end.对于“筛选法”的改进，主要也体现在两个方面枚举要筛选的质数和筛选的过程。2. 对要筛选的质数范围的改进假设要求的质数上限为N，那么显而易见，根据“枚举法”的一个结论，即一个数若不是质数，则必然含有小于的质因子。因此，“筛选法”所要枚举的质数仅仅限于的范围内，对于其他大于的质数，只需打印，无须进行“筛选”。改进后的程序如下：var i, j : integer; ok : array1.10000 of boolean;begin fillchar(ok,sizeof(ok),true); for i:=2 to 10000 do if oki then begin write(i:8); if i=round(sqrt(10000) then begin j:=2*i; while (j=10000) do begin okj:=false; inc(j,i); end; end; end;end.事实上，本次改进的效果并不是特别明显，因为，大于的质数即使进行筛选，由于其本身数值大，所以在N范围内可被筛选的数并不是很多。3. 对筛选过程的改进我们注意到，所有质数，除2以外，都是奇数。换句话说，所有偶数，除2以外，都不是质数。应用这个性质，我们将2作为特例进行特殊处理后，每次用求得的一个质数（必然为奇数）进行筛选时，不要2倍，3倍，4倍的筛选了，只要3倍，5倍，7倍筛选即可（因为奇数偶数偶数）。如此，“筛选法”效率从理论上就提高了1倍！程序如下：var i, j, a : integer; ok : array1.10000 of boolean;begin fillchar(ok,sizeof(ok),true); write(2:8); for i:=1 to 4999 do if ok2*i+1 then begin a:=2*i+1; j:=3; write(a:8); while j*a=10000 do j*a=10000涵盖了a= round(sqrt(10000)的条件 begin okj*a:=false; inc(j,2); end; end;end.至此，“筛选法”已经被改进得非常优秀了。事实上，“枚举法”和“筛选法”的改进之外还有许多，但编程的复杂度也会随之不断上升！（在竞赛中，求质数仅仅可能是某道题目的一个部分，应用上面的方法就已经足够了）三、枚举法与筛选法的比较这样，我们求质数时就有了两种不同的方法：“枚举法”和“筛选法”。现在，让我们从理论上来比较它们的运行效率。“枚举法”对于每个数都要枚举所有小于该数平方根的质数来判断，并根据最后改进的程序运行，比较次数见下表。上限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，的位置，这样可以节约一半的空间。具体程序如下：var i, j, a : integer; ok : array1.4999 of boolean;begin fillchar(ok,sizeof(ok),true); write(2:8); for i:=1 to 4999 do if oki then begin a:=2*i+1; j:=a; write(a:8); while j+i=4999 do begin okj+i:=false; j:=j+a; end; end;end.四、一个例子【例】有一个正整数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之间的所有素数，依次用素数去除被除数，直至被除数为1或除数超过指定范围。该算法用N一S图描述如图所示。 读入被除数N： For i:=1 to 65535 doI是素数？NoYes 计数器S:=0 当I能整除被除数 被除数:=被除数/I 计数器累加S0NoYes 输出I与S被除数等于1？NoYes 输出（“DATA ERROR”）参考程序如下：var i, j, len, lens, k, num : word; d : longint; ok : boolean; data : array1.7000 of word; su, tem : array1.120 of integer; fin, fout : text; st : s