Longest sub | 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
let allPrimes = new Set ( ) ; function simpleSieve ( limit , prime ) { let mark = Array . from ( { length : limit + 1 } , ( _ , i ) => 0 ) ; for ( let i = 2 ; i <= limit ; ++ i ) { if ( mark [ i ] == false ) { prime . push ( i ) ; for ( let j = i ; j <= limit ; j += i ) { mark [ j ] = true ; } } } } function primesInRange ( low , high ) { let limit = Math . floor ( Math . sqrt ( high ) ) + 1 ; let prime = [ ] ; simpleSieve ( limit , prime ) ; let n = high - low + 1 ; let mark = Array . from ( { length : n + 1 } , ( _ , i ) => 0 ) ; for ( let i = 0 ; i < prime . length ; i ++ ) { let loLim = Math . floor ( low / prime [ i ] ) ; loLim *= prime [ i ] ; if ( loLim < low ) { loLim += prime [ i ] ; } if ( loLim == prime [ i ] ) { loLim += prime [ i ] ; } for ( let j = loLim ; j <= high ; j += prime [ i ] ) mark [ j - low ] = true ; } for ( let i = low ; i <= high ; i ++ ) { if ( ! mark [ i - low ] ) { allPrimes . add ( i ) ; } } } function maxPrimeSubarray ( arr , n ) { let current_max = 0 ; let max_so_far = 0 ; for ( let i = 0 ; i < n ; i ++ ) { if ( ! allPrimes . has ( arr [ i ] ) ) current_max = 0 ; else { current_max ++ ; max_so_far = Math . max ( current_max , max_so_far ) ; } } return max_so_far ; } let arr = [ 1 , 2 , 4 , 3 , 29 , 11 , 7 , 8 , 9 ] ; let n = arr . length ; let max_el = Number . MIN_VALUE ; let min_el = Number . MAX_VALUE ; for ( let 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 ) ; document . write ( maxPrimeSubarray ( arr , n ) ) ;