[C/C++] Project Euler #50 - Consecutive Prime Sum

This problem itself is not particularly difficult. On the Project Euler website, its difficulty rating is listed as 5%.

Personally, I did not find the problem conceptually hard. However, trying to optimize the speed required a lot of careful thought.

The goal of the problem is to find the prime number within a given range that can be expressed as the sum of the most consecutive primes, where the sum itself is also a prime.

 

finding prime number

My initial approach was rather brute-force.  Although it was a naive method, I still tried to make it run as fast as possible.

---

Below is the source code I wrote for the brute-force method.

#define LIMIT   1000000

void solve1()
{
    static unsigned primes[LIMIT/2];
    unsigned pcount = 0;

    primes[pcount++] = 2;
    primes[pcount++] = 3;

    for( unsigned p = 5 ; p < LIMIT ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 1 ; primes[i]*primes[i] <= p ; i++ )
            if( p%primes[i] == 0 ) { isPrime = false; break; }
        if( isPrime ) primes[pcount++] = p;
    }
    int max = 1, maxv = 2;
    for( int i = 1 ; i < pcount ; i++ )
    {
        for( int j = 0 ; j < i-max ; j++ )
        {
            int sum = 0, k;
            for( k = 0 ; sum < primes[i] ; k++ ) sum += primes[j+k];
            if( sum == primes[i] && max < k ) { max = k; maxv = primes[i]; }
        }
    }
    printf("ans = %d(%d)\n", maxv, max);
}

Since it took too much time, I thought about ways to speed it up without completely overhauling the overall algorithmic structure. Because the problem deals with the sum of consecutive primes, I figured that precomputing and storing the cumulative sums could help improve performance.

However, several issues arose. As I was storing the cumulative sum of primes from the first prime up to the current one, I found that a 32-bit integer variable was insufficient. Therefore, I used 64-bit integers to store the cumulative sums of the primes.

---

The resulting source code looks like the one shown below.

//------------------------------------------------
//    Project Euler #50 - Consecutive Prime Sum
//        - by Aubrey Choi
//        - created at 2015-03-30
//        - modified : 2016-06-03
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

#define    LIMIT    1000000

void solve1()
{
    static unsigned primes[LIMIT/2];
    unsigned pcount = 0;

    primes[pcount++] = 2;
    primes[pcount++] = 3;

    for( unsigned p = 5 ; p < LIMIT ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 1 ; primes[i]*primes[i] <= p ; i++ )
            if( p%primes[i] == 0 ) { isPrime = false; break; }
        if( isPrime ) primes[pcount++] = p;
    }
    int max = 1, maxv = 2;
    for( int i = 1 ; i < pcount ; i++ )
    {
        for( int j = 0 ; j < i-max ; j++ )
        {
            int sum = 0, k;
            for( k = 0 ; sum < primes[i] ; k++ ) sum += primes[j+k];
            if( sum == primes[i] && max < k ) { max = k; maxv = primes[i]; }
        }
    }
    printf("ans = %d(%d)\n", maxv, max);
}

void solve2()
{
    static unsigned primes[LIMIT/2];
    static uint64_t primesum[LIMIT/2];
    unsigned pcount = 0;

    primesum[0] = 0;
    primes[pcount++] = 2;
    primesum[pcount] = 2;
    primes[pcount++] = 3;
    primesum[pcount] = 5;

    for( unsigned p = 5 ; p < LIMIT ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 1 ; primes[i]*primes[i] <= p ; i++ )
            if( p%primes[i] == 0 ) { isPrime = false; break; }
        if( isPrime ) 
        {
            primes[pcount++] = p;
            primesum[pcount] = primesum[pcount-1]+p;
        }
    }
    int max = 1, maxv = 2;
    for( int i = pcount-1 ; i > 0 ; i-- )
    {
        for( int j = 0 ; j < i-max ; j++ )
        {
            for( int k = j+max ; k < pcount ; k++ )
            {
                uint64_t sum = primesum[k] - primesum[j];
                if( sum > primes[i] ) break;
                if( sum == primes[i] ) 
                {
                    max = k-j;
                    maxv = primes[i];
                    break;
                }
            }
        }
    }
    printf("ans = %d(%d)\n", maxv, max);
}

int main()
{
    clock_t t;

    t = clock();
    solve1();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    t = clock();
    solve2();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    return 0;
}

In fact, on my computer, the execution time of solve1(...) is about 127.7 seconds, while solve2() runs in about 18.5 seconds. Although the speed is still not entirely satisfactory, it is clear that there has been a significant improvement compared to the initial algorithm.