且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

筛法求质数------------2012年12月30日

更新时间:2022-09-15 10:56:57

       问题描述:使用筛法求质数。有一个很神奇的筛子,可以给它一个数i,这个筛子有办法把i的所有倍数去掉。请用这个方法求出2到N之间的所有质数。要求,程序不能使用乘法和除法,只能用加或减,以求加快速度。
        该问题的思路来自《C语言名题精选百则技巧篇》,很惭愧,我对这样的涉及一些数学知识的题很少有解决的办法,我需要在这一方面加强。
        我把书中的思路归纳如下,并加上了我自己的一些想法。
        1.   2的倍数都不是质数,所以不比考虑2的倍数。2是质数,所以考虑的数的集合是   2i+3,i=0,1,2,3,4.......
        2.   求质数,只需要处理到num/2就可以了。在程序中MAX为基准,算出2到2*MAX+3之间的质数,实际也是处理到MAX就停止了。
        3.   程序不能使用乘法,只能使用加法和减法,所以就需要作一些数学方面的处理:2i+3是一个奇数,要去除它的倍数。在第1点中,已经去除了2的倍数,所以就不用管2i+3的偶数倍的数了,只需要处理2i+3的奇数倍的数了。所以,我们需要去除(2n+1)(2i+3),n=1,1,2,3,4....当然,不能去除2i+3本身。然后对(2n+1)(2i+3)做一个变形,朝着2N+3这样的形式去变形(ps:这是我以前在数学证明题中经常做的)。变形过程:(2n+1)(2i+3)=2n(2i+3)+2i+3=2[n(2i+3)+i]+3;这就是2N+3的形式了(N就是n(2i+3)+i)。由于在程序中我们是以i作为索引的,所以我们用筛子筛出为止为N的数,也就是删除位置为n(2i+3)+i的数。这样,就不难写出程序了。
        代码如下:
 1 #include <stdio.h>
 2 #define MAX 1000
 3 #define SAVE 0
 4 #define DELETE 1
 5 
 6 int sieve[1000]={0}; //all to SAVE
 7 
 8 int main()
 9 {
10     int i,k;
11     int prime;
12     int count=1;//The sum number of the prime numbers 
13     //2*i+3 is odd numbers
14     for(i=0;i<MAX;i++)
15     {
16         if(sieve[i]==SAVE) //it is a prime number 
17         {
18             //I have a problem here.Why are the front several numbers prime number after one or two sieve process such as 5 or 7 or 11? I just think they are prime nubmers without proving it.  
19             prime=i+i+3; 
20             count++;
21             for(k=prime+i;k<=MAX;k+=prime)
22                 sieve[k]=DELETE;
23         }
24     }
25     printf("%6d",2);
26 
27     for(i=0,k=2;i<MAX;i++)
28     {
29         if(sieve[i]==SAVE)
30         {
31             if(k>10) 
32             {
33                 printf("\n"); 
34                 k=1;
35             }
36             int temp=i+i+3;
37             printf("%6d",temp);
38             k++;
39         }
40     }
41     printf("\nThe sum number is %d \n",count);
42     return 0;
43 }
 
        总结:与一些数学变换相结合的程序题是我的一个弱项,自己总是想不到这样的想法,最根本的原因就是这样思考得太少了以及数学功底不够。在以后需要多加强数学知识的学习以及数学与程序相结合的算法(数据结构)甚至是项目实践等等练习。 


本文转自NeilHappy 51CTO博客,原文链接:http://blog.51cto.com/neilhappy/1104740,如需转载请自行联系原作者