patterncppMinor
Project Euler Problem #10
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.
As
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.