Find the prime numbers which can written as sum of most consecutive primes | C ++ program to find Longest Sum of consecutive primes ; utility function for sieve of sundaram ; In general Sieve of Sundaram , produces primes smaller than ( 2 * x + 2 ) for a number given number x . Since we want primes smaller than MAX , we reduce MAX to half This array is used to separate numbers of the form i + j + 2 ij from others where 1 <= i <= j ; Main logic of Sundaram . Mark all numbers which do not generate prime number by doing 2 * i + 1 ; Since 2 is a prime number ; Print other primes . Remaining primes are of the form 2 * i + 1 such that marked [ i ] is false . ; function find the prime number which can be written as the sum of the most consecutive primes ; To store maximum length of consecutive primes that can sum to a limit ; The prime number ( or result ) that can be represented as sum of maximum number of primes . ; Consider all lengths of consecutive primes below limit . ; if we cross the limit , then break the loop ; sum_prime [ i ] - sum_prime [ j ] is prime number or not ; Check if sum of current length of consecutives is prime or not . ; update the length and prime number ; Returns the prime number that can written as sum of longest chain of consecutive primes . ; Store prime number in vector ; Calculate sum of prime numbers and store them in sum_prime array . sum_prime [ i ] stores sum of prime numbers from primes [ 0 ] to primes [ i - 1 ] ; Process all queries one by one ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 10000 ; void sieveSundaram ( vector < int > & primes ) { bool marked [ MAX / 2 + 1 ] = { 0 } ; for ( int i = 1 ; i <= ( sqrt ( MAX ) - 1 ) / 2 ; i ++ ) for ( int j = ( i * ( i + 1 ) ) << 1 ; j <= MAX / 2 ; j = j + 2 * i + 1 ) marked [ j ] = true ; primes . push_back ( 2 ) ; for ( int i = 1 ; i <= MAX / 2 ; i ++ ) if ( marked [ i ] == false ) primes . push_back ( 2 * i + 1 ) ; } int LSCPUtil ( int limit , vector < int > & prime , long long int sum_prime [ ] ) { int max_length = -1 ; int prime_number = -1 ; for ( int i = 0 ; prime [ i ] <= limit ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( sum_prime [ i ] - sum_prime [ j ] > limit ) break ; long long int consSum = sum_prime [ i ] - sum_prime [ j ] ; if ( binary_search ( prime . begin ( ) , prime . end ( ) , consSum ) ) { if ( max_length < i - j + 1 ) { max_length = i - j + 1 ; prime_number = consSum ; } } } } return prime_number ; } void LSCP ( int arr [ ] , int n ) { vector < int > primes ; sieveSundaram ( primes ) ; long long int sum_prime [ primes . size ( ) + 1 ] ; sum_prime [ 0 ] = 0 ; for ( int i = 1 ; i <= primes . size ( ) ; i ++ ) sum_prime [ i ] = primes [ i - 1 ] + sum_prime [ i - 1 ] ; for ( int i = 0 ; i < n ; i ++ ) cout << LSCPUtil ( arr [ i ] , primes , sum_prime ) << " ▁ " ; } int main ( ) { int arr [ ] = { 10 , 30 , 40 , 50 , 1000 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; LSCP ( arr , n ) ; return 0 ; }