首页 > 代码库 > 数据结构与算法分析(C语言描述)习题2.14

数据结构与算法分析(C语言描述)习题2.14

问题描述:Eratosthenes筛是一种用于计算小于N的所有素数的方法。我们从制作整数2到N的表开始。我们找出最小的未被删除的整数i,打印i,然后删除i, 2i, 3i, ..., 当i > √N时,算法终止。

首先,没必要做2到N的表,在一个循环内遍历2到N即可。

其次,所谓最小也没必要判断,依次遍历时整数i自然是它到最后一个数之间的最小值。

最后,整数i是否被删除等价于整数i是否素数flag[i]==1或0表示,1表示素数,0表示非素数。

可以这么做:

遍历2到N的整数i,如果它是素数,打印它,然后删除它的倍数

i==2时删除2的倍数,等于3时删除3的倍数,等于5时删除5的倍数,... ,直到N为止。

 1 void Eratosthenes(int N) 2 { 3     char * flag; 4     int i, j; 5  6     flag = (char *)malloc(sizeof(char)*N); 7     memset(flag, 1, sizeof(char)*N); 8  9     for (i = 2; i < N; i++)10     {11         if (flag[i] == 1)12         {13             printf("%d\t", i);14             for (j = 2; j*i < N; j++)    //删除素数i的倍数15                 flag[j*i] = 0;16         }17     }18     free(flag);19 }

测试结果:

技术分享 其中数据IO花费了不少的时间。

这是筛选法最简单的思路之一,还可以继续优化,比如:因为除了2所有的偶数都不是素数,所以可以排除一半的数据量。也可以对外层循环只遍历到根号N,可以减小循环的规模。

数据结构与算法分析(C语言描述)习题2.14