优化素数表

所谓有素数筛选法，就是从2(最小的素数)开始往上进行筛选，把所有质数的整倍数都剔除掉，最后剩下来的就是素数了。当然这不是最好最快的方法，占用的空间也不小，不过这种方法简单易行，运行效率也不是太低——比起最普通的用函数判断每个数那也是天壤之别了，所以还是非常常用的。

有一处优化：筛选i的倍数时，可以直接从i^2开始筛选，因为比i^2小的倍数已经被比i小的素数给筛选掉了，因为这样，外层循环也可以只累加到sqrt(n)即可。另外一个Re_storage函数将素数表进行转存，便于某些情况下的访问，prime_count保存素数的个数。

C++ CODE:

#define MAXNUM 10000

bool prime[MAXNUM+1];

int prime2[MAXNUM+1];

int prime_count;

void Make ()

{

       int i,j;

       for ( i = 0 ; i <= MAXNUM ; i++ )

              prime[i] = true;

       prime[0] = prime[1] = false;

       int sq = sqrt (double(MAXNUM))+1 ;

       for ( i = 2 ; i <= sq ; i++ ) {

              if ( prime[i] == true ) {

                     for ( j = i*i ; j <= MAXNUM ; j+= i )

                            prime[j] = false;

              }

       }

}

void Re_storage ()

{

       prime_count = 0;

       for ( int i = 2 ; i <= MAXNUM ; i++ ) {

              if ( prime[i] )

                     prime2[prime_count++] = i;

       }

}

文章转自：http://blog.sina.com.cn/s/blog_787c1f7b0100s12x.html