0001 #include "Bitmap/Bitmap.h" //引入Bitmap结构 0002 0003 /****************************************************************************************** 0004 * 筛法求素数 0005 * 计算出不大于n的所有素数 0006 * 不计内循环,外循环自身每次仅一次加法、两次判断,累计O(n) 0007 * 内循环每趟迭代O(n/i)步,由素数定理至多n/ln(n)趟,累计耗时不过 0008 * n/2 + n/3 + n/5 + n/7 + n/11 + ... 0009 * < n/2 + n/3 + n/4 + n/6 + n/7 + ... + n/(n/ln(n)) 0010 * = O(n(ln(n/ln(n)) - 1)) 0011 * = O(nln(n) - nln(ln(n)) - 1) 0012 * = O(nlog(n)) 0013 * 如下实现做了进一步优化,内循环从i * i而非i + i开始,迭代步数由O(n / i)降至O(max(1, n / i - i)) 0014 ******************************************************************************************/ 0015 void Eratosthenes ( int n, char* file ) { 0016 Bitmap B ( n ); B.set ( 0 ); B.set ( 1 ); //0和1都不是素数 0017 for ( int i = 2; i < n; i++ ) //反复地,从下一 0018 if ( !B.test ( i ) ) //可认定的素数i起 0019 for ( int j = __min ( i, 46340 ) * __min ( i, 46340 ); j < n; j += i ) //以i为间隔 0020 B.set ( j ); //将下一个数标记为合数 0021 B.dump ( file ); //将所有整数的筛选标记统一存入指定文件,以便日后直接导入 0022 }