所有素数低于200万的总和

Question

我做了一个程序,返回200万以下所有素数的总和.我真的不知道这个是怎么回事,当得到正确的答案是142913828922时,我得到142891895587作为我的答案.似乎它缺少了几个素数.我很确定getPrime函数可以正常工作.我曾经使用它几次并且工作正常.代码如下:

vector<int> getPrimes(int number);

int main()
{

    unsigned long int sum = 0;
    vector<int> primes = getPrimes(2000000);

    for(int i = 0; i < primes.size(); i++)
    {
        sum += primes[i];
    }

    cout << sum;

    return 0;
}


vector<int> getPrimes(int number)
{

    vector<bool> sieve(number+1,false);
    vector<int> primes;
    sieve[0] = true;
    sieve[1] = true;

    for(int i = 2; i <= number; i++)
    {
        if(sieve[i]==false)
        {
            primes.push_back(i);
            unsigned long int temp = i*i;
            while(temp <= number)
            {
                sieve[temp] = true;
                temp = temp + i;
            }
        }
    }
    return primes;
}

Answer 1

表达式i*i溢出因为i是int.它在被分配之前被截断temp.为了避免溢出,施放它:static_cast<unsigned long>( i ) * i.

更好的是,在该条件发生之前终止迭代:for(int i = 2; i*i <= number; i++).

测试固定.

顺便说一下,你有点(不)幸运的是,这不会产生额外的素数而且会丢失一些素数:int值是有符号的,并且在溢出时可能是负数,并且通过我对§4.7/ 2的读数,这将导致内循环跳过.