Calculating sum of prime number below 2 million by using Sieve of Atkin

Question

I'm doing project Euler and I got this problem. I run the code in VS 2013 and the program crashes because of overflow.

This is my method:

void problem10()
{
    long long int iter = 2, sum = 0;

    //Sieve of Atkin
    bool isPrime[PRIME_LIMIT+1];

    for (long long int i = 5; i <= PRIME_LIMIT; i++)
    {
        isPrime[i] = false;
    }

    long long int lim = ceil(sqrt(PRIME_LIMIT));

    for (long long int x = 1; x <= lim; x++)
    {
        for (long long int y = 1; y <= lim; y++)
        {
            long long int n = 4 * x*x + y*y;
            if (n <= PRIME_LIMIT && (n % 12 == 1 || n % 12 == 5))
            {
                isPrime[n] = true;
            }

            n = 3 * x*x + y*y;
            if (n <= PRIME_LIMIT && (n % 12 == 7))
            {
                isPrime[n] = true;
            }

            n = 3 * x*x - y*y;
            if (x > y && n < PRIME_LIMIT && n % 12 == 11)
            {
                isPrime[n] = true;
            }
        }
    }

    // eliminate composites by seiving
    for (long long int n = 5; n <= lim; n++)
    {
        if (isPrime[n])
        {
            for (long long int k = n*n; k <= PRIME_LIMIT; k+= k*k)
            {
                isPrime[k] = false;
            }
        }
    }

    for (long long int n = 5; n <= PRIME_LIMIT; n++)
    {
        if (isPrime[n])
        {
            sum += n;
        }
    }
    sum = sum + 2 + 3;
    printf("%lld\n", sum);
    /* //A basic approach -- too slow
    while (iter < PRIME_LIMIT)
    {
        bool isDivisible = false;
        int prime = iter;
        for (int a = 2; a < iter; a++)
        {
            if (prime%a == 0)
            {
                isDivisible = true;
                break;
            }
        }

        if (isDivisible){}
        else
        {
            //printf("prime is: %d\n", prime);
            sum += prime;
        }
        iter++;
    }
    printf("Sum of prime is: %d\n", sum);
    */
}

This method includes 2 approaches to calculate the sum of all prime numbers in ranges PRIME_LIMIT. The second approach take too long to get the result, and probably take whole day. The first approach is using sieve of Atkin, the program crashes!

Is there any mistake in my code?? Please help!

Answer 1

So, let's talk about this problem:

Integer Sizes

Much like Java, Integers in C have a limit to the size that they can fit. Here, you chose to use a long long int. Luckily for this problem, the sum will fit in that data type. For other Project Euler problems, you will need to use a BigInt class.

Your Slow Approach

The slow approach is actually fine if you add one addition. We know, that the list of divisors that we need to search, is actually less than all of the numbers from 2 ... n. So we can change one of your loops to this:

int max = ciel(sqrt(iter));
for (int a = 2; a < max; a++)
    if (prime % a == 0)
        isDivisible = true;
        break;

If we do that, your code will finish relatively quickly.

Your Fast Approach

I haven't fully gone through this code, because it doesn't look like the sieve of eratosthenes that I remember, but at the very least, you are going to overflow the stack with your allocations.

#define PRIME_LIMIT 2000000
bool isPrime[PRIME_LIMIT+1];

Let's fix that:

#define PRIME_LIMIT 2000000
static bool isPrime[PRIME_LIMIT+1]

Or:

#define PRIME_LIMIT 2000000
bool *isPrime = calloc(PRIME_LIMIT + 1, sizeof(bool));

Recommendations

I'd really recommend to not start by trying to implement the Sieve of Atkin. If I was to implement this as a learning exercise, I'd do it in this order:

1. The slow approach that you've done above. In python, similar code takes about 1 minute to solve the problem. I'd suspect C could do it in about 10 seconds (or faster).

2. The sieve of eratosthenes is a much simpler sieve to implement. I'd recommend using that next.

3. Then try to implement the sieve of atkin. An algorithm of that speed is completely unnecessary for a problem of this size though.