eratosthenes筛选法

来源:转载

写下从2至某个上限的之间的所有整数,在算法的剩余部分,你遍历整个列表并剔除所有不是质数的整数。

找到列表中的第一个不被剔除的整数(也就是2),然后将列表后面所有逢双的数都剔除,因为它们可以被2整除,接着,再回到列表头部重新开始,此时列表中尚未被剔除的第一个元素是3,所以在3之后把每逢第3个数剔除,再回到列表开头,以此类推,反复进行,最后列表中的未被剔除的全为质数。

先考虑实现最简单的这样一种功能,后面我们将改良这个算法:

 

 1 #include<stdio.h> 2 #include<stdlib.h> 3 #define SIZE 1000 4 #define FALSE 0 5 #define TRUE 1 6 7 int 8 main() 9 {10 char sieve[SIZE]; //筛选数组11 char * sp; 12 int number; //用来表示数字13 int sum=0;14 15 for(sp=&sieve[0];sp<&sieve[SIZE];sp++) //将数组所有的值初始化为真16 *sp=TRUE;17 18 for(number=2;;number++) //在循环内部设置退出循环19 {20 sp=&sieve[0]+number-2; //将指针指向第一个数21 if(sp>=&sieve[SIZE]) 22 break;23 while(sp+=number,sp<&sieve[SIZE]) //往后跳number个数并将其置024 {25 *sp=FALSE;26 }27 }28 for(number=2,sp=&sieve[0];sp<&sieve[SIZE];number++,sp++) //29 { 30 if(*sp)31 {32 sum++;33 printf("%d/t",number);34 }35 if(sum%5==0)36 printf("/n");37 }38 printf("the total of count is:%d",sum);39 40 }

这样得到1000内有168个质数。

这个算法需要筛选数组的第一个数为质数,在上面的代码中为2,事实上,我们可以节省一点空间,因为偶数除了2以外都不是质数,所以我们可以直接从奇数入手,这样,可以找的范围就扩大了一倍,稍微改一下以上的代码即可:

 1 #include<stdio.h> 2 #include<stdlib.h> 3 #define SIZE 1000 4 #define FALSE 0 5 #define TRUE 1 6 7 int 8 main() 9 {10 char sieve[SIZE]; 11 char * sp; 12 int number; 13 int sum=0;14 15 for(sp=&sieve[0];sp<&sieve[SIZE];sp++)16 *sp=TRUE;17 18 for(number=3;;number+=2) //改变初值及遍历奇数19 {20 sp=&sieve[0]+(number-3)/2; //注意是第一个数21 if(sp>=&sieve[SIZE])22 break;23 while(sp+=number,sp<&sieve[SIZE])24 {25 *sp=FALSE;26 }27 }28 for(number=3,sp=&sieve[0];sp<&sieve[SIZE];number+=2,sp++) //注意循环量的改变29 { printf("2/n"); //2也为质数30 if(*sp)31 {32 sum++;33 printf("%d/t",number);34 }35 if(sum%5==0)36 printf("/n");37 }38 printf("the total of count is:%d",++sum); //2也为质数39 40 }

 这样我们可以得到在2000以内有303个质数。



分享给朋友:
您可能感兴趣的文章:
随机阅读: