Problem 50: Consecutive prime sum

*Difficulty: Medium

Problem:

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

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

How to solve:

1.Brute force

Create a list of prime numbers which is smaller than 1000000, iterate each prime number p in the list, check all possible consecutive prime numbers than can add up to form the p. If it is, and the consecutive length is bigger than the previous one, then update the maximum consecutive length as well as the prime number holding that length.
Solution took so damn long, more than 90 seconds.
There are many ways to create a list of prime numbers, here I was using sieve Eratosthenes. Screen Shot 2016-07-05 at 2.11.32 AM

Then brute force

Screen Shot 2016-07-05 at 2.12.38 AM

2.Using consecutive prime sum property

Accidentally, I come up with this table

Screen Shot 2016-07-05 at 2.16.27 AM

For example, if you want to calculate consecutive sum from 2 to 5,

we can do it just by take the consecutive sum from 2 of 5 = 10, subtract it from consecutive sum from 2 of 2 = 2, the result is 8, then add 2 to the result, which produces 10.

Let f(n) is the consecutive prime sum from 2 of a number n , then the consecutive sum from i to j (inclusive) is f(j) – f(i)+i , the consecutive length is j – i +1

The first step is creating a prime number list, and f(n) of each prime . (We can do as exactly as the brute force method).

Then apply the formula above, we got

Screen Shot 2016-07-05 at 2.25.13 AM

Took  11114 ms

It’s 2:30 AM, i’m so tired so I cannot write fast code. You can make it better, can’t you? :>

Advertisements