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( Rank n, char* file ) {
0015    Bitmap B( n ); B.set( 0 ); B.set( 1 ); // 0和1都不是素数
0016    for ( Rank i = 2; i * i < n; i++ ) //逐个地
0017       if ( !B.test( i ) ) //确认下一个素数i
0018          for ( Rank j = i * i; j < n; j += i ) //并将一系列能被i整除的
0019             B.set( j ); // j标记为合数（小于i*i的合数，必在此之前已被标记）
0020    B.dump( file ); //将筛选标记统一存入指定文件，以便日后直接导入
0021 }