10亿素数算法

unsigned int PrimeCounter(unsigned long MaxNumber)
{
const unsigned MachineLength = sizeof(unsigned int) << 3;
const unsigned int MaxSize = MaxNumber / (MachineLength<<1) + 1;
unsigned int* Number = new unsigned int[MaxSize];
memset(Number,0xFF,MaxSize*sizeof(unsigned int));
for(unsigned int num = 3;num<MaxNumber;num+=2)
if(Number[num/(MachineLength<<1)] & (0x1L<<((num>>1) % MachineLength))) {
unsigned int NotPrime = num * num;
if ((NotPrime / num == num))
for(;NotPrime < MaxNumber ;NotPrime += num )
if(NotPrime % 2)
Number[NotPrime / (MachineLength<<1)] &= ~(0x1L << ((NotPrime>>1) % (MachineLength)));
else
continue;
}
unsigned int counter = 1;
for(unsigned int num = 3;num < MaxNumber;num +=2)
if( Number[num /(MachineLength<<1)] & (0x1L<<(num>>1 % (MachineLength)))){
//cout << num << "/t";
counter ++;
}
delete []Number;
return counter;
}



int main()
{
//计算10亿需要60MB内存,比普通的bit位算法节省一半内存
//计算1亿约为2秒
clock_t pretime = clock();
cout << "/nPrimeCounter(100000000)= "<<PrimeCounter(100000000) << endl;
cout << clock() - pretime <<" ms has used.";
cout <<endl;
system("pause");
return 0;
}
出处：http://blog.csdn.net/atlight/archive/2008/12/28/3630846.aspx