Longest sub | Java program to find longest subarray of prime numbers ; To store the prime numbers ; Function that find prime numbers till limit ; Find primes using Sieve of Eratosthenes ; Function that finds all prime numbers in given range using Segmented Sieve ; Find the limit ; To store the prime numbers ; Comput all primes less than or equals to sqrt ( high ) using Simple Sieve ; Count the elements in the range [ low , high ] ; Declaring boolean for the range [ low , high ] ; Traverse the prime numbers till limit ; Find the minimum number in [ low . . high ] that is a multiple of prime [ i ] ; Mark the multiples of prime [ i ] in [ low , high ] as true ; Element which are not marked in range are Prime ; Function that finds longest subarray of prime numbers ; If element is Non - prime then updated current_max to 0 ; If element is prime , then update current_max and max_so_far ; Return the count of longest subarray ; Driver code ; Find minimum and maximum element ; Find prime in the range [ min_el , max_el ] ; Function call
import java . util . * ; import java . lang . * ; import java . io . * ; class GFG { static Set < Integer > allPrimes = new HashSet < > ( ) ; static void simpleSieve ( int limit , ArrayList < Integer > prime ) { boolean [ ] mark = new boolean [ limit + 1 ] ; for ( int i = 2 ; i <= limit ; ++ i ) { if ( mark [ i ] == false ) { prime . add ( i ) ; for ( int j = i ; j <= limit ; j += i ) { mark [ j ] = true ; } } } } static void primesInRange ( int low , int high ) { int limit = ( int ) Math . floor ( Math . sqrt ( high ) ) + 1 ; ArrayList < Integer > prime = new ArrayList < > ( ) ; simpleSieve ( limit , prime ) ; int n = high - low + 1 ; boolean [ ] mark = new boolean [ n + 1 ] ; for ( int i = 0 ; i < prime . size ( ) ; i ++ ) { int loLim = ( int ) Math . floor ( ( double ) low / ( int ) prime . get ( i ) ) ; loLim *= ( int ) prime . get ( i ) ; if ( loLim < low ) { loLim += ( int ) prime . get ( i ) ; } if ( loLim == ( int ) prime . get ( i ) ) { loLim += ( int ) prime . get ( i ) ; } for ( int j = loLim ; j <= high ; j += ( int ) prime . get ( i ) ) mark [ j - low ] = true ; } for ( int i = low ; i <= high ; i ++ ) { if ( ! mark [ i - low ] ) { allPrimes . add ( i ) ; } } } static int maxPrimeSubarray ( int [ ] arr , int n ) { int current_max = 0 ; int max_so_far = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! allPrimes . contains ( arr [ i ] ) ) current_max = 0 ; else { current_max ++ ; max_so_far = Math . max ( current_max , max_so_far ) ; } } return max_so_far ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 4 , 3 , 29 , 11 , 7 , 8 , 9 } ; int n = arr . length ; int max_el = Integer . MIN_VALUE ; int min_el = Integer . MAX_VALUE ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] < min_el ) { min_el = arr [ i ] ; } if ( arr [ i ] > max_el ) { max_el = arr [ i ] ; } } primesInRange ( min_el , max_el ) ; System . out . print ( maxPrimeSubarray ( arr , n ) ) ; } }