首页 > 代码库 > 数据结构与算法分析(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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。