Project Euler #50: Consecutive prime sum

This article is part of a series where I'll be diving head first into the Project Euler puzzles. I want to document the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that I mean I can't look up any other implementations online. After the implementation, I will validate the answer by using this document or a similar sheet.

In this article I'll be solving: Project Euler #50.

Introduction “Which prime, below one-million, can be written as the sum of the most consecutive primes?”

Part 1: Sieve of Eratosthenes To generate all the primes under 1.000.000, I’ll be using a sieve. The reason for this, is because it’s a faster method of generating prime numbers than using a standard for loop and checking each individual number. The sieve of Eratosthenes goes something like this:

fn sieve_of_erato(n: usize) -> Vec<bool> {
    let mut primes = vec![true; n + 1];
    let max = (n as f64).sqrt() as usize;

    for i in 2..=max {
        if primes[i] {
            let mut j = i.pow(2);
            while j <= n {
                primes[j] = false;
                j += i
            }
        }
    }

    primes
}

#[test]
fn test_sieve_of_erato() {
    let sieves = sieve_of_erato(20);
    assert_eq!(sieves[2], true);
    assert_eq!(sieves[4], false);
}

It generates a vector of the first 1.000.000 primes in 0.1s, which is quite fast.

Part 2: Each consecutive The puzzle is looking for consecutive groups of primes, meaning we have to write an each_cons()-loop. At first my idea was to take the method from “Substring divisibility”, however this method proves to be a tad slow, especially since we have to sum each subgroup, while increasing the group size. A couple of smart things we can do:

To show the second point in code:

// Slow variation
let max_l = primes.len() - chain_length;

for p in 1..max_l {
    let mut sum: usize = primes[p..p + chain_length].iter().sum();

    // Test if sum is prime
}
// Fast variation
let max_l = primes.len() - chain_length;
let mut sum: usize = primes[0..chain_length].iter().sum();

for p in 1..max_l {
    sum += primes[p - 1 + chain_length];
    sum -= primes[p - 1];

    // Test if sum is prime
}

Nitting it together The full code goes something like this: firstly, I’ll use the sieve of Eratosthenes, to generate a list of the first primes under 1.000.000. The next part is where I’ll create an unspecified loop (since I’ve no idea what the max chain length is going to be), where we add 1 to chain_length each cycle and test if any of the consecutive groups of primes is a prime. If it is, store it in max_prime. Once the initial sum, becomes higher than 1.000.000, stop the loop, because there’s no point in continuing any further.

const MAX_N: usize = 1_000_000;

fn problem_50() -> u64 {
    let mut chain_length = 21;
    let mut max_prime = 0;

    let sieve = sieve_of_erato(MAX_N);
    let mut primes = vec![];

    for n in 2..sieve.len() {
        if sieve[n] {
            primes.push(n);
        }
    }

    loop {
        let max_l = primes.len() - chain_length;
        let mut sum: usize = primes[0..chain_length].iter().sum();

        // If the initial sum goes over 1m, stop!
        if sum > MAX_N {
            break;
        }

        for p in 1..max_l {
            sum += primes[p - 1 + chain_length];
            sum -= primes[p - 1];

            if sum < sieve.len() && sieve[sum] {
                max_prime = sum;
            }
        }

        chain_length += 1;
    }

    max_prime as u64
}

#[test]
fn test_problem_50() {
    assert_eq!(problem_50(), 997651);
}

Solved!

The full solution is available on GitHub.

55545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321