0

我正在研究一个相对简单的问题，该问题基于将某个值下的所有素数相加。我写了一个程序来完成这个任务。我正在使用长类型变量。当我达到更高的数字（~200/300k）时，我用来跟踪总和的变量变为负数，尽管没有添加负值（基于我的知识和我所做的一些测试） . 数据类型是否有问题，或者我遗漏了什么。

我的代码如下（在 C++ 中）[向量基本上是一个动态数组，以防人们想知道]：

bool checkPrime(int number, vector<long> & primes, int numberOfPrimes) {
    for (int i=0; i<numberOfPrimes-1; i++) {
        if(number%primes[i]==0) return false;
    }
    return true;
}

long solveProblem10(int maxNumber) {
    long sumOfPrimes=0;
    vector<long> primes;
    primes.resize(1);
    int numberOfPrimes=0;
    for (int i=2; i<maxNumber; i++) {
        if(checkPrime(i, primes, numberOfPrimes)) {
            sumOfPrimes=sumOfPrimes+i;
            primes[numberOfPrimes]=long(i);
            numberOfPrimes++;
            primes.resize(numberOfPrimes+1);
        }
    }
    return sumOfPrimes;
}
4

5 回答 5

3

整数表示值使用二进制补码，这意味着最高位表示符号。当您将数字相加足够高时，最高位被设置（整数溢出）并且数字变为负数。

您可以通过使用unsigned long（32 位，并且可能仍会溢出您要求和的值）或使用unsigned long long（64 位）来解决此问题。

于 2013-10-17T20:34:21.487 回答
2

尽管没有添加负值，但我用来跟踪总和的变量变为负数（基于我的知识和我所做的一些测试）

longs 是有符号整数。在 C++ 和其他低级语言中，整数类型具有固定大小。当您添加超过它们的最大值时，它们将溢出并环绕为负数。这是由于二进制补码如何工作的行为。

于 2013-10-17T20:34:01.770 回答
0

long您的系统上可能只有 32 位 -uint64_t用于求和 - 这为您提供了一个有保证的 64 位无符号整数。

#include <cstdint>

uint64_t sumOfPrimes=0;
于 2013-10-17T20:33:05.073 回答
0

检查有效的整数值：变量。数据类型。

您正在使用signed long，通常是 32 位，即 -2kkk - 2kkk，您可以使用 0-4kkk，也可以unsigned long使用 64 位(un)signed long long

如果您需要更大的值 2^64 (unsigned long long)，您将需要使用bignum 数学

于 2013-10-17T20:34:08.470 回答
0

您可以包含标头<cstdint>并使用类型 std::uintmax_t 而不是 long。

于 2013-10-17T20:40:44.443 回答