筛选法求素数VIP专享VIP免费

质数算法大全，及C 程序实现优化详解 筛选法 三木追风 质数的定义 一个数，如果只有1 和它本身两个因数，这样的数叫做质数，又称素数。 在上文 《素数算法大全，及C 程序实现优化详解 (一) 试除法》中我们已经探讨了求解素数的一类算法，并且将试除法从最初的低效版本优化的高效的V2。那么，还有没有其它更佳算法呢？这就是下面三藏要和大家探讨的内容 合数过滤筛选法 算法描述：我们知道，素数N 不能被 2~(N-1)间的任何数整除；反过来看，只要能被 2~(N-1)间的任何数整除的N，都不是素数。所以我们可以采用一个简单的排除法：就是对 N 以内的所有数，只要逐个去除值为 2~(N-1)的倍数的数，剩下的就是素数。 C 语言实现 // 合数过滤筛选法 Ver1 // 参数：n 求解n 以内(包括 n)的素数 // 返回值：n 以内素数个数 int CompositeNumFilterV1(int n) { int i, j; // 素数数量统计 int count = 0; // 分配素数标记空间，结合后文思考为何+1 char* flag = (char*)malloc( n+1 ); // 初始化素数标记 for (i=2; i<=n; i++) { // 为什么*(p+i)要写成flag[i]呢？可读性更佳尔 flag[i] = 1; } // 写程序要注意排版和留空，方便阅读，也可减少出错几率 // 以2~(N-1) 为因子过滤合数 for (i=2; i < n; i++) { for (j=2; i*j <= n; j++) { // i*j是由i,j 两整数相乘而得，显然不是素数 flag[i*j] = 0; } } // 统计素数个数 for (i=2; i<=n; i++) { // 其实if(flag)就其同样作用了，但这么写是有留言的 // 请参阅《 C 语言程序设计常见错误剖析及解决之道》一文 if (1 == flag[i]) count++; } // 因输出费时，且和算法核心相关不大，故略 // 释放内存，别忘了传说中的内存泄漏 free(flag); return count; } 在上文给出的main 函数中以不同参数调用CompositeNu mFilterV1 函数，得到执行结果如下： [100000]以内素数个数：9592, 计算用时：15 毫秒 [1000000]以内素数个数：78498, 计算用时：125 毫秒 [5000000]以内素数个数：348513, 计算用时：2578 毫秒 [10000000]以内素数个数：664579, 计算用时：6281 毫秒 注：因程序是非独占性运行的，所以时间不是完全精确的，但基本能反映实情 显然，比上文中的试除法要快，而且谁都可以看到上例是一个未经优化的粗陋版本，好多地方是三藏故意采用比较低效做法，为了与后文的...