Find sum of prime numbers using Sieve of Eratosthenes

Question

I' using Sieve to calculate the sum of all prime number below 2 million, but the program keeps crashing after trying several times due to overflow. It works fine with PRIME_LIMIT = 200000

So what is the problem in my code? I don't think that's the algorithm problem. When I put static keyword when declaring the boolean array, it prints out the wrong sum ... without the keyword, it's overflow ...

This is the method I wrote:

void problem10()

    {
        unsigned long long int iter = 2, sum = 0;

        static bool prime[PRIME_LIMIT];

        for (unsigned long long int i = 0; i < PRIME_LIMIT; i++)
        {
            prime[i] = true;
        }

        unsigned long long int limit = ceil(sqrt(PRIME_LIMIT));

        for (unsigned long long int i = 2; i <= limit; i++)
        {
            if (prime[i])
            {
                for (unsigned long long int j = i*i; j < PRIME_LIMIT; j += i)
                {
                    prime[j] = false;
                }
            }
        }

        for (unsigned long long int i = 2; i < PRIME_LIMIT; i++)
        {
            if (prime[i])
            {
                sum += i;
                //printf("Primes are: %d\n", i);
            }
        }
            printf("Sum of prime is: %llu\n", sum);
    }

Without `static`, the `bool prime[PRIME_LIMIT]` array is probably too large to be allocated on the *heap*, this causes the crash. – With `static`, it should work and actually produces the correct result in my test. — Martin R, Apr 12 '14 at 20:50
The code works for me when I include enough headers (``, ``, ``) and provide a `main()` that calls the function (and remove unused variable `iter`). The result is `Sum of prime is: 142913828922` when compiled for 32-bit or 64-bit on Mac OS X 10.9.2 with GCC 4.8.2. ` — Jonathan Leffler, Apr 12 '14 at 20:51
Correction: The array is too large to be allocated on the *stack*. But that was already explained in the answer to your previous question http://stackoverflow.com/questions/22969072/calculating-sum-of-prime-number-below-2-million-by-using-sieve-of-atkin. — Martin R, Apr 12 '14 at 20:56
"wrong sum" — what does it print? What do you expect it to print? How do you know it's wrong? — n. m. could be an AI, Apr 12 '14 at 20:57
For PRIME_LIMIT = 200000 I get 1709600813 when compiled for 32-bit on Windows 7 with Visual Studio 2012, with and without `static` before `bool prime`. @JonathanLeffler: strange I get not the same result as you. — Jabberwocky, Apr 12 '14 at 20:58
@MichaelWalz: 1709600813 is the sum of all primes up to 200.000, 142913828922 is the sum of the primes up to 2.000.000. — Martin R, Apr 12 '14 at 21:00
@MichaelWalz: I was testing PRIME_LIMIT of 2000000 (two million), not 200000 (two hundred thousand). — Jonathan Leffler, Apr 12 '14 at 21:01
Oops, now we have revealed the solution of a [Project Euler](http://projecteuler.net/about) problem :-) — Martin R, Apr 12 '14 at 21:02
well when i run the code, it give a different result for each time i run ... — Trung Bún, Apr 12 '14 at 21:28

score 3 · Accepted Answer · answered Apr 12 '14 at 21:43

3

As you said in a comment, you did not include <math.h>. Then the compiler does not know the declarations of the sqrt() and ceil() functions:

double sqrt(double x);
double ceil(double x);

and you probably got warnings about "implicitly declared functions".

The compiler then assumes that these functions return an int and will therefore generate wrong code which can cause any kind of undefined behavior.

answered Apr 12 '14 at 21:43

Martin R

529,903
94
1,240
1,382

Thank you! I learnt C from a Java programmer's view. I'm using VS 2013 and I'm a bit curious that why the compiler (intelligent sense feature of VS) doesn't give me an error when I use a function from a library that wasn't included in the code? – Trung Bún Apr 12 '14 at 21:47
No, it didn't give me that error. It just compile perfectly and give me random number each time – Trung Bún Apr 12 '14 at 21:48
1

@TrungBún: It *is allowed* to call a function without declaring it first (for historic compatibility reasons). GCC and Clang give compiler *warnings* in that case. I do not have VS here, so I cannot explain why you don't get a warning. – Martin R Apr 12 '14 at 21:53

Find sum of prime numbers using Sieve of Eratosthenes

1 Answers1