C++中的大數問題

我正在研究一個相對簡單的問題，它基於將某個特定值下的所有素數加在一起。我寫了一個應該完成這個任務的程序。我正在使用長型變量。當我進入更高的數字（〜200/300k）時，我用來跟蹤總和的變量變爲負數，儘管沒有負值被添加到它（基於我的知識和我已經完成的一些測試）。數據類型是否存在某些問題或者我缺少某些內容。C++中的大數問題

我的代碼是下面（在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; 
}

來源

2013-10-17 user2892137

整數溢出。它總是整數溢出。 :) – Mysticial

long可能只有32位在系統上 - 使用uint64_t的總和 - 這給你一個保證的64位無符號整數。

#include <cstdint> 

uint64_t sumOfPrimes=0;

來源

2013-10-17 20:33:05

我使用跟蹤和變量變成儘管沒有負值被添加到其負（根據我的知識和一些測試中，我所做的）

多頭是有符號整數。在C++和其他低級語言中，整數類型的大小是固定的。當你添加超過他們的最大值時，它們會溢出並繞到負數。這是由於twos complement如何工作的行爲。

來源

2013-10-17 20:34:01

檢查有效的整數值：Variables. Data Types.

您使用signed long，通常是32位，這意味着-2kkk - 2kkk，既可以使用unsigned long，這是0-4kkk，或使用64位(un)signed long long

如果需要更大的值2^64（無符號長長），則需要使用bignum math

來源

2013-10-17 20:34:08

整數代表值使用two's complement這意味着該最高階位表示符號。當您將數字增加到足夠高時，將設置最高位（integer overflow），並且數字變爲負數。

您可以通過使用unsigned long（32位，並且仍可能與您正在求和的值溢出）或使用unsigned long long（即64位）來解決此問題。

來源

2013-10-17 20:34:21 Steve

您可以包含標頭<cstdint>並使用類型std :: uintmax_t而不是long。

來源

2013-10-17 20:40:44

C++中的大數問題

回答

相關問題