Find the prime numbers which can written as sum of most consecutive primes


Given an array of limits. For every limit, find the prime number which can be written as the sum of the most consecutive primes smaller than or equal to limit.

The maximum possible value of a limit is 10^4.


Below are steps.

  1. Find all prime numbers below a maximum limit (10^6) using Sieve of Sundaram and store them in primes[].
  2. Construct a prefix sum array prime_sum[] for all prime numbers in primes[]
    prime_sum[i+1] = prime_sum[i] + primes[i].
    Difference between two values in prime_sum[i] and prime_sum[j] represents sum of consecutive primes from index i to index j.
  3. Traverse two loops , outer loop from i (0 to limit) and inner loop from j (0 to i)
  4. For every i, inner loop traverse (0 to i), we check if current sum of consecutive primes (consSum = prime_sum[i] – prime_sum[j]) is prime number or not (we search consSum in prime[] using Binary search).
  5. If consSum is prime number then we update the result if the current length is more than length of current result.

Below is implementation of above steps.



Be the first to comment

Leave a Reply