We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #50: Consecutive prime sum
Project Euler #50: Consecutive prime sum
Contest ends in
Sort by
recency
|
30 Discussions
|
Please Login in order to post a comment
I tried in cpp it works and passed all testcases...
This is my python solution for this question but only 5 testcases will be passed......
java code
import java.util.Scanner;
public class Solution {
}
Hmmm... Test case 9 failed, the answer is wrong. What is this? BTW what is the correct answer for 2: 2 1? @shashank21j
Update: Never mind, I've found out the issue, I had a bug in my binary search implementaion.
Here is how I did it:
Use Sieve of Eratosthenes to generate enough primes to add up to above max N (10^12). I did 10 million. (This involves some hueristics)
Make an "is_prime" function. It's fast enough to use the results of the Sieve, check if Number is prime prime by checking if primes up to square_root(Number) divide Number.
Say primes start with index 0, [p_0, p_1, p_2, ...] = [2, 3, 5, ...]
Theorem: If you add consecutive primes starting from index, i, and the prime consecutive sum, S_i, with maximum number of components has X many components, then any sum with X components that start at index greater than i will be greater than S_i.
Strategy: Start with index i = 0, find prime consecutive sum, S_0 < n, with maximum number of components. The sum has X compoments. Now increment i, i = 1. Start looking for sums that have X+1 number of components with the first S_1 sum above S_0: S_0 - p_0 + p_X. find prime consecutive sum, S_1 < n which maximizes number of components (at least X+1), and if no such sum exists then S_0 remains the sum with most components. Continue to incriment i and look for sums with increasing number of components.
IMPORTANT HEURISTIC: Calculating S_0 is the hardest part and S_1, S_2, ... will start off with the progress of S_0. S_0 will often be close to n. Therefore, to calculate S_0, instead of checking increasing consecutive sums to see if they are prime, start from the back by first calculating the largest consecutive sum of primes less than n and then subtracting primes until you get a prime sum. This will greatly reduce the use of the "is_prime" function.