问题描述
我做了一个程序,返回的所有素数在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 。
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万以下的总和的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!