Algorithm returns garbage when input is too large?

Question

I started working on Project Euler problems today to keep myself busy over break. One of the problems asks for the sum of all prime numbers below 2 million, so I threw together a Sieve of Eratosthenes to find all those numbers.

unsigned long i, j, sum = 0, limit = 2000000;

// Allocate an array to store the state of numbers (1 is prime, 0 is not).
int* primes = malloc(limit * sizeof(int));

// Initialize every number as prime.
for (i = 0; i < limit; i++)
    primes[i] = 1;

// Use the sieve to check off values that are not prime.
for (i = 2; i*i < limit; i++)
    if (primes[i] != 0)
        for (j = 2; i*j < limit; j++)
            primes[i*j] = 0;

// Get the sum of all numbers still marked prime.
for (i = 2; i < limit; i++)
    if (primes[i] != 0)
        sum += i;

printf("%d", sum);

This works perfectly up to limit around half a million. After this, it returns random values (for example, 1000000 returns -1104303641). I've tried declaring all the unsigned long variables as unsigned long long to no avail. The error seems to be happening in the last 4 lines, because primes[] contains nothing but 1's and 0's at that point. I figure this has something to do with the size of the values being worked with, can anyone offer any guidance?

@totymedli: Are you really suggesting that the OP should allocate an array of two million longs on the stack?? — ruakh, Dec 11 '12 at 04:04
what size is long on your platform? printf("%d\n", sizeof(long)); — xaxxon, Dec 11 '12 at 04:07
have you tried a different format string? %l instead of %d? or maybe %ul for unsigned long? — Ken, Dec 11 '12 at 04:08
I just ran this and it looks good on my mac. Change the printf at the end of ld and I get: 142913828922 -- which is inline with what daniel fischer said — xaxxon, Dec 11 '12 at 04:13
The sum of the primes `<= N` is roughly `N²/(2*log N)`. So for `N = 2000000`, that's a bit more than 10^11 and doesn't fit in a 32-bit integer. — Daniel Fischer, Dec 11 '12 at 04:14
That's your problem then. You're on a 32-bit platform. You're going to need some sort of third-party long-int. See my answer below. — xaxxon, Dec 11 '12 at 04:34

Bill Lynch · Answer 1 · 2012-12-11T04:13:08.923

6

Wolfram Alpha tells me that the sum of the primes less than 500000 is 9914236195.

That number doesn't fit in a 32 bit integer, so you're overflowing an int during your sum loop. You could try to use a uint64_t, but that problem will eventually occur again with a high enough limit (although I suspect that a limit of 2000000 will fit).

edited Dec 11 '12 at 04:13

answered Dec 11 '12 at 04:00

Bill Lynch

80,138
16
128
173

What `int`, the index of the array? How do I change that to `uint64_t`? – St. Hand Dec 11 '12 at 04:16
no, there is no need to change the index of the array. Only the sum, but that's already a long – xaxxon Dec 11 '12 at 04:19
Looks like you can't run that query for 2000000 unless you have a pro account. Standard computation time exceeded... – xaxxon Dec 11 '12 at 04:20

score 3 · Accepted Answer · edited May 23 '17 at 11:48

3

Change the %d to %ld and you should get:

142913828922

which seems like it should be (close to or) the right answer.

..assuming your longs aren't 32-bit.

If you're on a 32-bit platform, you're going to need some sort of third-party big int library.

BigInteger in C?

recommends: http://gmplib.org/

edited May 23 '17 at 11:48

Community

1
1

answered Dec 11 '12 at 04:04

xaxxon

19,189
5
50
80

Changing %d to %ld or %ul yields 1179908154, which is indeed closer to the right answer. – St. Hand Dec 11 '12 at 04:23

Algorithm returns garbage when input is too large?

2 Answers2