HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Project Euler Problem #10

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
problemprojecteuler

Problem

I've read other solutions about solving the 10th problem for Project Euler (finding the sum of all prime numbers under 2,000,000) but I wanted to try it on my own using the Sieve of Eratosthenes method. It runs quickly and it seems to work for all of my test increments (under 10, first 1000 primes) but it doesn't seem to work for the full 2,000,000 range. I was wondering if anyone could help point out the problem in my code. I know it's not the prettiest/most efficient code, so sorry.

#include 

using namespace std;

int main(int argc, char const *argv[])
{
    // upper limit & sum
    int sum = 0;
    int upLimit = 2000000;

    // array of isPrime check for integers
    bool isPrime[upLimit+1];

    // initialize
    for (int i=2; i <= upLimit; i++) {
        isPrime[i] = true;
    }

    for (int i=2; i<=upLimit; i++) {
        if (isPrime[i]) {
            // add to sum
            sum += i;

            // mark all multiples
            int j = i;
            while (j <= upLimit) {
                isPrime[j] = false;
                j += i;
            }
        }
    }
    cout << sum << endl;
}

Solution

You need to check for overflow before adding.

for (int i=2; i::max() - sum <= i) {
            std::cerr << "Overflow" << std::endl;
            return 1;
        }

        // add to sum
        sum += i;
        …


As int is only guaranteed to hold values up to 32767, you'll find that you should use a long long for sum.

Code Snippets

for (int i=2; i<=upLimit; i++) {
    if (isPrime[i]) {
        // Check for overflow
        if (std::numeric_limits<decltype(sum)>::max() - sum <= i) {
            std::cerr << "Overflow" << std::endl;
            return 1;
        }

        // add to sum
        sum += i;
        …

Context

StackExchange Code Review Q#75765, answer score: 3

Revisions (0)

No revisions yet.