求质数之除余法

redraiment, 2007-02-06

问题描述

　　试编写一个程序，找出 2→N 之间的所有质数（质数的概念请看这里），用尽可能快的方法实现。

问题分析

　　这个问题可以有两种解法：一种是用“筛子法”，另一种是从 2→N 逐一检测出质数。

　　如果要了解“筛法”，请看另一篇文章《求质数之筛法》。

　　现在来介绍第二种方法。用这种方法，最先想到的就是让从2→N逐一检查。如果是就显示出来，如果不是，就继续检查下一个直到超出范围 N。这是正确的做法，但效率却不高。当然，2 是质数，那么 2 的倍数就不是质数，如果令 i 从 2→N，就很冤枉地测试了 4、6、8……这些数？所以第一点改建就是只测试 2 与所有的奇数

就足够了。同理，3 是质数，但6、9、12……这些 3 的倍数却不是，因此，如果能够把 2 与 3 的倍数跳过去而不测试，任意连续的 6 个数中，就只会测试 2 个而已。以6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5 为例，6n, 6n+2, 6n+4 是偶数，又 6n+3 是 3 的倍数，所以如果 2 与 3 的倍数都不理会，只要测试的数就只留下6n+1和6n+5而已了，因而工作量只是前面想法的 2/6 = 1/3，应该用这个方法编程。

　　还有个问题，就是如果判断一个数 i 是否为素数。按素数的定义，也就是只有 1 与本身可以整除，所以可以用 2→i-1 去除 i，如果都除不尽，i 就是素数。观点对，但却与上一点一样的笨拙。当 i>2 时，有哪一个数可以被 i-1 除尽的？没有！为什么？如果 i 不是质数，那么 i=a×b，此地 a 与 b 既不是 i 又不是 1；正因为 a>1，a 至少为 2，因此 b 最多也是 i/2 而已，去除 i 的数用不着是 2→i-1，而用 2→i/2 就可以了。不但如此，因为 i=a×b，a 与 b 不能大于 sqrt(i)，为什么呢？如果 a>sqrt(i)，b>sqrt(i)，于是 a×b > sqrt(i)*sqrt(i) = i，因此就都不能整除i了。如果i不是质数，它的因子最大就是 sqrt(i)；换言之，用 2→sqrt(i)去检验就行了。

　　但是，用 2→sqrt(i) 去检验也是浪费。就像前面一样，2 除不尽，2 的倍数也除不尽；同理，3 除不尽，3 的倍数也除不尽……最理想的方法就是用质数去除i。

　　但问题是这些素数从何而来？这比较简单，可以准备一个数组 prime[]，用来存放找到的素数，一开始它里面有 2、3、5。检查的时候，就用 prime[] 中小于 sqrt(i)的数去除 i 即可，如果都除不尽，i 就是素数，把它放如 prime[] 中，因此 prime[] 中的素数会越来越多，直到满足个数为止！

　　不妨用这段说明来编写这个程序，但是程序设计的时候会有两个小问题：

如果只检查 6n+1 和 6n+5 ？不难发现，它们的距离是4、2、4、2……所以，可以先定义一个变量 gab=4，然后 gab=6-gab;
比较是不能用 sqrt(i)，因为它不精确。举个例子，i=121，在数学上，sqrt(i) 自然是 11，但计算机里的结果可能是 10.9999999，于是去除的数就是 2、3、5、7，而不含 11，因此 121 就变成质数了。解决这个问题的方法很简单，不要用开方，用平方即可。例如，如果 p*p<=i，则就用 p 去除 i。而且它的效率比开方高。

程序清单

#include <stdlib.h>
#include <stdio.h>

int creat_prime ( int prime[], int n, int total )
{
   int i, *p, g = 2;

   for ( i = 7; i <= n; i += g ) {
   g = 6 - g;
   p = prime;
   while ( (*p) * (*p) <= i && i % (*p) ) {
   p++;
   }
   if ( i % (*p) ) {
   prime[total++] = i;
   }
   }

   return total;
}

int main(void)
{
   int prime[30000] = { 2, 3, 5 };
   int total = 3; /* 找到素数的个数 */
   int n = 200000; /* 要查找的范围(>=6) */
   int i;

   total = creat_prime ( prime, n, total );
   for ( i = 0; i < total; i++) {
   printf ( "%d ", prime[i] );
   if ( i && !(i % 10) )
   putchar ( '\n' );
   }
   putchar ( '\n' );

   return EXIT_SUCCESS;
}

贪玩的程序员

搜索此博客