Find the prime numbers which can written as sum of most consecutive primes | Java program to find longest sum of consecutive primes ; Store prime number in vector ; 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 . ; 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 code
import java . util . * ; class GFG { static int MAX = 10000 ; static ArrayList < Object > primes = new ArrayList < Object > ( ) ; static void sieveSundaram ( ) { boolean [ ] marked = new boolean [ MAX / 2 + 1 ] ; Arrays . fill ( marked , false ) ; for ( int i = 1 ; i <= ( Math . sqrt ( MAX ) - 1 ) / 2 ; i ++ ) for ( int j = ( i * ( i + 1 ) ) << 1 ; j <= MAX / 2 ; j = j + 2 * i + 1 ) marked [ j ] = true ; primes . add ( 2 ) ; for ( int i = 1 ; i <= MAX / 2 ; i ++ ) if ( marked [ i ] == false ) primes . add ( 2 * i + 1 ) ; } static int LSCPUtil ( int limit , long [ ] sum_prime ) { int max_length = - 1 ; int prime_number = - 1 ; for ( int i = 0 ; ( int ) primes . get ( i ) <= limit ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( sum_prime [ i ] - sum_prime [ j ] > limit ) break ; long consSum = sum_prime [ i ] - sum_prime [ j ] ; Object [ ] prime = primes . toArray ( ) ; if ( Arrays . binarySearch ( prime , ( int ) consSum ) >= 0 ) { if ( max_length < i - j + 1 ) { max_length = i - j + 1 ; prime_number = ( int ) consSum ; } } } } return prime_number ; } static void LSCP ( int [ ] arr , int n ) { sieveSundaram ( ) ; long [ ] sum_prime = new long [ primes . size ( ) + 1 ] ; sum_prime [ 0 ] = 0 ; for ( int i = 1 ; i <= primes . size ( ) ; i ++ ) sum_prime [ i ] = ( int ) primes . get ( i - 1 ) + sum_prime [ i - 1 ] ; for ( int i = 0 ; i < n ; i ++ ) System . out . print ( LSCPUtil ( arr [ i ] , sum_prime ) + " ▁ " ) ; } public static void main ( String [ ] arg ) { int [ ] arr = { 10 , 30 , 40 , 50 , 1000 } ; int n = arr . length ; LSCP ( arr , n ) ; } }