0001 #include "Bitmap/Bitmap.h" //引入Bitmap结构 0002 0003 /****************************************************************************************** 0004 * 筛法求素数:找出小于n的所有素数 0005 * 内循环每趟迭代O(n/i)步,外循环由素数定理至多n/ln(n)趟,累计耗时不过 0006 * n/2 + n/3 + n/5 + n/7 + n/11 + ... 0007 * < n/2 + n/3 + n/4 + n/6 + n/7 + ... + n/(n/ln(n)) 0008 * = O(n(ln(n/ln(n)) - 1)) 0009 * = O(nln(n) - nln(ln(n)) - 1) 0010 * = O(nlog(n)) 0011 * 如下实现中,内循环的起点、外循环的终点都了优化 0012 ******************************************************************************************/ 0013 0014 void Eratosthenes ( int n, char* file ) { 0015 Bitmap B( n ); B.set( 0 ); B.set( 1 ); //0和1都不是素数 0016 for ( int i = 2; i*i < n; i++ ) //逐个地 0017 if ( !B.test ( i ) ) //确认下一个素数i 0018 for ( int j = i * i; j < n; j += i ) //并将一系列能被i整除的 0019 B.set ( j ); //j标记为合数(小于i*i的合数,必在此之前已被标记) 0020 B.dump ( file ); //将筛选标记统一存入指定文件,以便日后直接导入 0021 }