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.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #50: Consecutive prime sum
You are viewing a single comment's thread. Return to all comments →
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.