C语言精选名题百则——第二章（数字问题）

问题2.3求质数（PRIME1.C )

试编写一个程序，找出前N (如200)个质数。如果没有进一步要求，这不是难题。 但在此希望从所知的、使用除法的方法中，用最快的办法来编写程序。

【说明】

可能最先想到的办法，就是让某个变量i从2变到N,然后检查它是不是质数，如果是就显示出来，如果不是，就检查下一个。这是正确的做法，但却没有注意到一个小细节, 因而使程序运行速度变慢。当然，2是质数，但所有2的倍数都不是质数，如果令i从2 变到N,不就很冤枉地测试了 4，6,8,10，…这些数？所以第一点提示是测试2，3，5，7，…，N，即 2与所有奇数就足够了。同理，3是质数，但6,9,12，…这些3的倍数却不是，因此，如果能够把2与3的倍数都跳过去而不测试，任意连续的6个数中，就只会测试两个而已。以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是如上述的一个数（不是2与3的倍数)，如何测试i是个质数呢？按照定义，i 如果是质数，也就只有1与i可以除尽自己，所以可以用2,3,4,5,6，…，i-1去除i,如果都除 不尽（余数不是0), i就是质数。观点也对，但却与上一点一样地笨拙。当i>2时，有哪 1个数i可以被i-1除尽的？没有，为什么？如果i不是质数，那么i=a*b,此地a与b既 不是i又不是1;正因为a>1，a至少是2，因此b最多是i/2而已，去除i的数用不着是 2，3，4，…i-1；而用2，3，4,…,i/2就可以了。不但如此，因为i=a*b，a与b不能大于i^½，为什么呢？如果i不是质数,它的因子最大就是换言之，用2，3，4，5，…，i^½去除i就行了。

但是，用2,3，4，5，…，i^½去除 i 也是个浪费。就像是前一段所说的，2除不尽，2的倍数 也除不尽；同理，3除不尽，3的倍数也除不尽……最理想的方法就是用质数去除i，因为 在前一段的提示，i不是2与3的倍数，所以就用5，7，11，13，17，19，…这些比 i^½ 小的质数去 除i即可。但问题是这些质数从何而来？这比较简单，可以准备一个数组prime[]，用来存放找出来的质数，一开始它应该有2、3与5。于是当i=5,7,11，13，17,19,23,25,29，…这些不是2与3 的倍数时，就用prime[]中小于 i^½ 的数去除 i 即可，如果都除不尽，i就是质数，把它放入 prime[]中，因此prime[]中的质数雜会越来越多，直到满足所要的个数为止。

不妨用这段说明来编写程序，不过应注意下面几点：

(1)不要处理2与3的倍数（见第一段)。

(2)用质数去除（见第二、三段）。

(3)用i^½可能会有问题，为什么？有什么方法可以解决？

【解答】

程序的结构本身并不复杂，只解释几个重点而已。

第一，看如何跳过2与3的倍数。在问题说明中，看过在6n，6n + 1，6n+2，611+3，6n+4 与6n+5中，只有6n+1与6n+5要做测试，看看是否是质数，看看这两个数的相对位置。上一组最后一个要测试的值，与这一组第一个要测试的值的距离是2; 而同一组中要测试的两个值之间的距离是4。所以从5起，依次加2、加4、加2、加4、… 就可以得到5，7，11，13，17，19，…这些要测试的值了。但是2+4=6,可以用一个变量（程序中是 gap),令它的值在开始时为2,下一个值就是6-gap (就是4),再下次6-gap不就是2了 吗？这就是程序中gap=6-gap的意义。

第二，不能比较是否小于i^½，原因是对某些i而言，i^½可能并不精确。举个例子，如 果i=121，在数学上i^½自然是11,但是计算机算出来的结果很可能是10.999999，于是去 除i的数就是2，3，5，7而不含11，因此变成121是个质数了。解决之道很简单，不要用开方， 用平方即可。例如，如果p*q<i，就用p去除，这就一定不会出现上面的问题。不但如此，平方的运算时间也一定会比开方有效率。

【程序说明】

在程序中，prime[]是用来存放找出来的质数的，一开始时就有了 2，3，5这3个最基本 的质数（都小于6)。gap的初值是2，它的值依次是2，4，2，4，…，在解答中见过了。Count 计算到目前为止一共找到了多少个质数，2,3，5已经放入prime[],所以count的值是3。于 是当count比MAXSIZE小的时候，就产生下一个要检查的数，存入may一be一prime,进入 for循环做检查工作；如果是个质数，那么for循环中的if就永远是假，is一prime的值就不曾被改变，因此就把它存入prime[]中，这就是程序的基本结构。

#include <stdio.h>

#define MAXSIZE  100
#define YES		 1
#define NO		 0
 
int main()
{
	int prime[MAXSIZE];
	int gap =2;
	int count=3;
	int may_be_prime=5;
	int i,is_prime;
	
	prime[0]=2;
	prime[1]=3;
	prime[2]=5;
	
	while(count<MAXSIZE)
	{
		may_be_prime +=gap;
		gap=6-gap;
		is_prime=YES;
		for(i=2;prime[i]*prime[i]<=may_be_prime && is_prime;i++)
		{
			if(may_be_prime %prime[i] == 0)
				is_prime=NO;
		}
		if(is_prime)
			prime[count++]=may_be_prime;
	}
	
	 printf("\nPrime Number Generation Program");
     printf("\n===============================\n");
     printf("\nFirst %d Prime Numbers are :\n", count);
     for (i = 0; i < count; i++) {
          if (i % 10 == 0) printf("\n");
          printf("%5d", prime[i]);
     }
	
	return 0;
}