一般来说，判断一个正整数n是不是质数，通常我们的办法是：
1 将n用2~n-1来整除，如果能被整除，则不是质数；
2 对方法1优化一下，除数上限可以由n-1缩小到n^0.5；
判断某一个数差不多用上面的方法，按现在计算机的速度，就是一眨眼的功夫就计算出来了。
现在，我们需要求2~n中所有的质数，怎么办呢？
一种比较笨的方法，也就是参考求单个质数的办法写的程序，即是让i循环取2~n的值，用i整除比它小的所有质数来判断i是否是质数，如果都不可整除，则i是质数。
源代码如下：
/*
用质数相除法求所有质数的算法
bocai @ 2012.08.15
目前测试用时如下：
MAXI time(s)
2^24 8
2^25 28
2^26 55
速度比筛选法慢多了。
*/
#include <stdio.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <iostream>
#include "time.h"
using namespace std;
int main(void)
{
// 理论：一个数是质数，则它一定不能被小于它的质数所整除
const size_t maxI = 67108864;// 2^26 测试上限
vector<int> czs; // 当前算出来的质数
czs.reserve(maxI / 20); // 当maxi较大时，质数量一般小于5%
czs.push_back(2); // 2先放进去
size_t index; // 索引变量
bool isIzs; // 当前验证的数是否是质数
size_t sqrg = 2; // 平方计数
size_t sqrs = (size_t)pow(sqrg, 2); // 平方数
size_t i = 3; // 从2开始算质数
cout << "start time: " << time(NULL) <<endl;
while(i < maxI)
{
index = 0;
isIzs = true; // 标识i是否是质数
while(czs[index] < sqrg) // 还可以验证的质因数 注意index++
{
if(i % czs[index] == 0) // 被整除
{
isIzs = false; // 被整除，则不是质数
break;
}
index++;
}
if(isIzs && i != sqrs)
{
czs.push_back(i);
}
if(i == sqrs) // 达到了计数
{
sqrg++;
sqrs = (int)pow(sqrg, 2);
}
i++;
}
cout << "end time: " << time(NULL) <<endl;
cout << " max i:" << maxI << " count:" << czs.size() << endl;
/* for(i = 0; i < czs.size(); i++)
{
cout << "\t" << czs[i];
}
*/
return 0;
}一看这样不行啊，在虚拟机中，才2^26次方就用了55秒，太慢了。
上网一查，说是最快的方法是筛选法，于是研究一下，实现之，果然快了。筛选法的源码如下：
/*
用筛选法求所有质数的算法
bocai @ 2012.08.15
目前测试用时如下：
MAXI time(s)
2^24 3
2^25 8
2^26 12
2^27 26
2^28 52
2^29 108
2^30 222
2^31 514
2^32 982
*/
#include <stdio.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <iostream>
#include "time.h"
#include <bitset>
using namespace std;
int main(void)
{
// #define MAXI 2147483648 // 2^31
const size_t MAXI = 4294967295; // 2^32-1
bitset<MAXI> *bs = new bitset<MAXI>(); // 为1表示当前索引所表示的数为质数
bs->set(); // 预置所有位都为1
bs->reset(0); // 置0索引0 1
bs->reset(1);
size_t pos = 2;
size_t npos; // pos的倍数索引
cout << "start time: " << time(NULL) <<endl;
while(pos < MAXI)
{
if(bs->test(pos)) // pos是质数，把后面它的倍数的全置0
{
npos = pos + pos; // 从2倍起
while(npos > pos // 预防溢出情况
&& npos < MAXI)
{
bs->reset(npos);
npos += pos; // 循环
}
}
pos++;
}
cout << "end time: " << time(NULL) <<endl;
cout << " max i:" << (MAXI - 1) << " count:" << bs->count() << endl;
/* for(int i = 2; i < bs.size(); i++)
{
if(bs.test(i))
{
cout << "\t" << i;
}
}
*/
return 0;
}在源代码级别不知还有没优化的地方，请多指教。