# Project Euler #50: Consecutive prime sum

# Project Euler #50: Consecutive prime sum

stbrumme + 2 comments Implementation hints:

- you need a prime test for large numbers. I use Miller-Rabin (like most of us).
- add your standard prime sieve (which should be able to generate the first 400000 primes).

**Major algorithmic hint**: I was surprised to find that all relevant chains start at very small primes. The first prime number of any chain is <= 131 (!). Knowing this you should be able to easily solve all test cases.Note: even N=2 is a sum/chain (with only one element, though)

arshad2117 + 0 comments Is there any way to solve this without considering the fact that all such chains start with a small prime?

linyu203 + 0 comments Nice hints.

kitchent + 0 comments Spent a lot of time on this problem, and got 100.00 without much satisfaction. I could be wrong, but I cannot see how using Miller-Rabin is significantly better than a simple

`is_prime(n)`

function when you have all the primes up to`sqrt(n)`

already available after a prime sieve.

armogur + 0 comments just for the record: under 100 million there are only 1392 records exists

andres_jaanson + 0 comments At first I felt this task is really difficult, almost unsolvable but once I found the longest possible chain starting with 2 and which is prime and less then or equal to 10**12. Then I realized this task is not that hard.

So if you feel stuck or just have no ideas. Then build an algorithm which finds the result mentioned before and I believe you will know how to continue.

vish_14 + 1 comment sum([7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89])=953 sum([23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]) = 983 983 is also a prime number, then why the ans is 953 not 983?

kedavamaru + 0 comments The first sum has a longer chain of primes, the problem ask for the longest chain, not for the largest sum

SOKS33 + 1 comment Hmmm I'm having trouble in getting 100% passed. TImeout for TC 1, 7 & 8 while all the others are running fine in 0.9 or 1s (It takes me 0.9s to generate 20M primes )

I can get an answer for 10**12 quite fast I guess, but can't handle 10 LARGE entries, as I'm sure at least one of those TC do this.

Can't find a way to memo results as my algorithm is made for just one N at a time

nhl4000 + 0 comments My Python 3 code had the same issue for Test Case #1, 7, 8. Time limit exceeded.

Ran it using Pypy 3 compiler and passed all cases.

jack239 + 0 comments Heuristics, heuristics, heuristics. Correctly has tuned algorithm, I got 100. Why did not anybody mention Sieve of Eratosthenes?

CMadhuVarun + 1 comment Forgive my ignorance, But isn't 983 the highest number below 1000 when consecutive prime numbers are added? In the problem section, they gave 953 as the highest number. Can anyone tell me how?

sum((2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 109)) = 983

sum((2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 241)) = 953

Can anybody tell me the prime numbers for 953?

Thank you

recurze + 0 comments sum([7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89])=953

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 109] is not a list of consecutive primes as the next prime after 83 is 89.

selindek + 1 comment I create sieve for 6000000, use the Miller-Rabin for above, but still need about 15 sec in JAVA.

If I limit my table for about max 100000 consecutive sums, then no timeout, but it's good only for the first 7 testcases.

jyotirmaysahoo21 + 1 comment You can reduce the size of sieve.By observation,I got that sum of first 126000 primes exceeds 10^12 and for that we need a sieve for 1700000(not exactly). I think this will help.

tygrys66681 + 0 comments Sum of first 126000 primes is 10^11. ( http://wolframalpha.com/input/?i=sum+of+first+126000+primes ) For 10^12 sum you need about 380000 primes and sieve for 6*10^6. Anyway - such sieve (even simple implementation) should be pretty fast (make sure you start marking non-primes with i*i).

welcometors + 0 comments A combination of Miller-Rabin and Prime-Sieve will give answer in a blink of an eye.

Spent alot of time in debugging, because of bug in overflow safe mod multiplication, make sure your modular functions are correct.

Sort 22 Discussions, By:

Please Login in order to post a comment