Longest sub | C # 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
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static HashSet < int > allPrimes = new HashSet < int > ( ) ; static void simpleSieve ( int limit , ref ArrayList prime ) { bool [ ] mark = new bool [ limit + 1 ] ; Array . Fill ( mark , false ) ; 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 prime = new ArrayList ( ) ; simpleSieve ( limit , ref prime ) ; int n = high - low + 1 ; bool [ ] mark = new bool [ n + 1 ] ; Array . Fill ( mark , false ) ; for ( int i = 0 ; i < prime . Count ; i ++ ) { int loLim = ( int ) Math . Floor ( ( double ) low / ( int ) prime [ i ] ) ; loLim *= ( int ) prime [ i ] ; if ( loLim < low ) { loLim += ( int ) prime [ i ] ; } if ( loLim == ( int ) prime [ i ] ) { loLim += ( int ) prime [ i ] ; } for ( int j = loLim ; j <= high ; j += ( int ) prime [ 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 = Int32 . MinValue ; int min_el = Int32 . MaxValue ; 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 ) ; Console . Write ( maxPrimeSubarray ( arr , n ) ) ; } }