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;
}

 

全部评论

相关推荐

躺尸修仙中:因为很多92的也去卷中小厂,反正投递简历不要钱,面试不要钱,时间冲突就推,不冲突就面试积累经验
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务