CODEWITHSUNDEEP
c++long-integer
user2892137
user2892137

Reputation: 1

Large Number Issues in C++

I'm working on a relatively simple problem based around adding all the primes under a certain value together. I've written a program that should accomplish this task. I am using long type variables. As I get up into higher numbers (~200/300k), the variable I am using to track the sum becomes negative despite the fact that no negative values are being added to it (based on my knowledge and some testing I've done). Is there some issue with the data type or I am missing something.

My code is below (in C++) [Vector is basically a dynamic array in case people are wondering]:

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

Upvotes: 0

Views: 881

Answers (5)

Vlad from Moscow
Vlad from Moscow

Reputation: 310910

You can include header <cstdint> and use type std::uintmax_t instead of long.

Upvotes: 0

Paul R
Paul R

Reputation: 212929

long is probably only 32 bits on your system - use uint64_t for the sum - this gives you a guaranteed 64 bit unsigned integer.

#include <cstdint>

uint64_t sumOfPrimes=0;

Upvotes: 0

Steve
Steve

Reputation: 7271

Integers represent values use two's complement which means that the highest order bit represents the sign. When you add the number up high enough, the highest bit is set (an integer overflow) and the number becomes negative.

You can resolve this by using an unsigned long (32-bit, and may still overflow with the values you're summing) or by using an unsigned long long (which is 64 bit).

Upvotes: 3

Iłya Bursov
Iłya Bursov

Reputation: 24145

check valid integer values: Variables. Data Types.

you're using signed long, which is usually 32 bit, which means -2kkk - 2kkk, you can either use unsigned long, which is 0-4kkk, or use 64 bit (un)signed long long

if you need values bigger 2^64 (unsigned long long), you will need to use bignum math

Upvotes: 0

Doug T.
Doug T.

Reputation: 65589

the variable I am using to track the sum becomes negative despite the fact that no negative values are being added to it (based on my knowledge and some testing I've done)

longs are signed integers. In C++ and other lower-level languages, integer types have a fixed size. When you add past their maximum they will overflow and wrap-around to negative numbers. This is due to the behavior of how twos complement works.

Upvotes: 2

Related Questions