所有素数在200万以下的总和 [英] Sum of all primes under 2 million

问题描述

我做了一个程序，返回的所有素数在200万以下的总和。我真的不知道这是怎么回事，我得到142891895587作为我的答案，当正确的答案是142913828922。它看起来像它缺少几个素数在那里。我很确定getPrime函数工作，因为它是应该的。我用了几次之前，工作正确比。代码如下：

I made a program that returns the sum of all primes under 2 million. I really have no idea what's going on with this one, I get 142891895587 as my answer when the correct answer is 142913828922. It seems like its missing a few primes in there. I'm pretty sure the getPrime function works as it is supposed to. I used it a couple times before and worked correctly than. The code is as follows:

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;
}

推荐答案

c> i * i 溢出，因为 i 是 int 。它在分配给 temp 之前被截断。为了避免溢出，转换它： static_cast （i）* i 。

The expression i*i overflows because i is an int. It is truncated before being assigned to temp. To avoid the overflow, cast it: static_cast<unsigned long>( i ) * i.

在该条件发生前终止迭代： for（int i = 2; i * i <= number; i ++）。

Even better, terminate iteration before that condition occurs: for(int i = 2; i*i <= number; i++).

测试已修复。

顺便说一句，你很幸运，这不会产生额外的素数以及缺少一些： int 值已签名，并且在溢出时可能为负值，根据我的§4.7/ 2的读数，这将导致内循环跳过。

Incidentally, you're kinda (un)lucky that this doesn't produce extra primes as well as missing some: the int value is signed, and could be negative upon overflow, and by my reading of §4.7/2, that would cause the inner loop to skip.

这篇关于所有素数在200万以下的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！