素数 算法 筛选法 那里错了?该怎么处理

素数 算法 筛选法 那里错了?
下面这个常见的素数筛选算法 在算前十万内都是极为正常的 也是正确的
但是算100万位时居然出错了
我真不明白.如果算法有问题也不应当到100万位后才出错
如果说 unsigned int放不下也不可能啊. 还没到40亿呢.
PrimeCounter(1百万) 返回值是78491 正确答案是784981
这里只是差几个而已 但在算千万时就差很多了 
我在网上查了下.千万内的素数是 664579 个
而这个程序算出的居然是 664116 两者相差463个呢....

C/C++ code

unsigned int PrimeCounter(unsigned int MaxNumber){    const unsigned MachineLength = sizeof(unsigned int);    const unsigned int MaxSize = MaxNumber / MachineLength + MachineLength;    unsigned int* Number = new unsigned int[MaxSize];    memset(Number,0xAA,MaxSize*sizeof(unsigned int));    for(unsigned int num = 3;num<MaxNumber;num+=2)        if( Number[num / MachineLength] & (0x1L<<(num % MachineLength)))            for(unsigned int NotPrime = num * num;NotPrime < MaxNumber;NotPrime += num<<1)                Number[NotPrime / MachineLength] &= ~(0x1L << NotPrime % MachineLength);        unsigned int counter = 1;    for(unsigned int num = 3;num < MaxNumber;num +=2)        if( Number[num / MachineLength] & (0x1L<<(num % MachineLength))){            counter ++;        }    delete []Number;    return counter;}int main(){    cout << "PrimeCounter(100)= "<<PrimeCounter(100) << endl;    cout << "PrimeCounter(1000)= "<<PrimeCounter(1000) << endl;    cout << "PrimeCounter(10000)= "<<PrimeCounter(10000) << endl;    cout << "PrimeCounter(100000)= "<<PrimeCounter(100000) << endl;    cout << "PrimeCounter(1000000)= "<<PrimeCounter(1000000) << endl;    cout << "PrimeCounter(10000000)= "<<PrimeCounter(10000000) << endl;    cout <<endl;    system("pause");    return 0;}

程序运行结果是: 
PrimeCounter(100)= 25
PrimeCounter(1000)= 168
PrimeCounter(10000)= 1229
PrimeCounter(100000)= 9592
PrimeCounter(1000000)= 78491
PrimeCounter(10000000)= 664116





[解决办法]
就是因为num*num溢出了的原因;
百万的平方早超出40亿了;

for(unsigned int NotPrime = num * num;NotPrime < MaxNumber;NotPrime += num<<1)
==>

unsigned int NotPrime = num * num;
if (NotPrime/num==num)
for(;NotPrime < MaxNumber ;NotPrime += num << 1)




[解决办法]
确实有乘法溢出了

C/C++ code

unsigned int PrimeCounter(unsigned int MaxNumber){    const unsigned MachineLength = sizeof(unsigned int);    const unsigned int MaxSize = MaxNumber / MachineLength + MachineLength;    unsigned int* Number = new unsigned int[MaxSize];    memset(Number,0xAA,MaxSize*sizeof(unsigned int));    for(unsigned int num = 3;num<MaxNumber;num+=2)    {        if(num > sqrt(MaxNumber))//这里加一句        {            break;        }        if( Number[num / MachineLength] & (0x1L<<(num % MachineLength)))            for(unsigned int NotPrime = num * num;NotPrime < MaxNumber;NotPrime += num<<1)                Number[NotPrime / MachineLength] &= ~(0x1L << NotPrime % MachineLength);    }        unsigned int counter = 1;    for(unsigned int num = 3;num < MaxNumber;num +=2)        if( Number[num / MachineLength] & (0x1L<<(num % MachineLength))){            counter ++;        }    delete []Number;    return counter;} 

 

查看更多 下一篇