3

我做了一个程序，它返回所有小于 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;
}
4

5 回答 5

10

表达式i*i溢出，因为iis an int。它在分配给 之前被截断temp。为避免溢出，请将其强制转换：static_cast<unsigned long>( i ) * i.

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

测试固定。

顺便说一句，你有点（不）幸运的是，这不会产生额外的素数并且会丢失一些：int值是有符号的，并且在溢出时可能是负数，并且通过我阅读§4.7/2，这将导致要跳过的内循环。

于 2010-05-10T04:44:41.920 回答
2

您可能会遇到数据类型限制：http ://en.wikipedia.org/wiki/Long_integer 。

于 2010-05-10T04:19:21.500 回答
1

这条线是问题所在：

unsigned long int temp = i*i;
于 2010-05-10T04:38:30.273 回答
0

我给你一个提示。仔细看看你给的初始值temp。您排除的第一个值是什么sieve？是否i还应排除其他较小的倍数？您可以使用哪些不同的初始值来确保跳过所有正确的数字？

您可以使用一些技巧来帮助自己解决这个问题。一种是尝试使用下限让您的程序正常工作。试着用 30 代替 200 万。它足够小，你可以用手快速计算出正确答案，甚至可以一次一行地在纸上完成你的程序。这会让你发现事情开始出错的地方。

另一种选择是使用调试器逐行遍历您的程序。调试器是强大的工具，尽管它们并不总是很容易学习。

您可以在程序进行时打印出消息，而不是使用调试器来跟踪您的程序。比如说，让它打印出结果中的每个数字，getPrimes而不是只打印总和。（这是您想先尝试下限的另一个原因——以避免被输出量所淹没。）

于 2010-05-10T04:48:08.653 回答
0

您的平台必须有 64 位长。这一行：

unsigned long int temp = i * i;

计算不正确，因为 i 被声明为 int 并且乘法结果也是 int（32 位）。强制乘法变长：

unsigned long int temp = (unsigned long int) i * i;

在我的系统上，long 是 32 位的，所以我必须同时更改temp和sum成为unsigned long long.

于 2010-05-10T06:00:41.013 回答