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
#include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_set < int > allPrimes ; void simpleSieve ( int limit , vector < int > & prime ) { bool mark [ limit + 1 ] ; memset ( mark , false , sizeof ( mark ) ) ; for ( int i = 2 ; i <= limit ; ++ i ) { if ( mark [ i ] == false ) { prime . push_back ( i ) ; for ( int j = i ; j <= limit ; j += i ) { mark [ j ] = true ; } } } } void primesInRange ( int low , int high ) { int limit = floor ( sqrt ( high ) ) + 1 ; vector < int > prime ; simpleSieve ( limit , prime ) ; int n = high - low + 1 ; bool mark [ n + 1 ] ; memset ( mark , false , sizeof ( mark ) ) ; for ( int i = 0 ; i < prime . size ( ) ; i ++ ) { int loLim = floor ( low / prime [ i ] ) ; loLim *= prime [ i ] ; if ( loLim < low ) { loLim += prime [ i ] ; } if ( loLim == prime [ i ] ) { loLim += prime [ i ] ; } for ( int j = loLim ; j <= high ; j += prime [ i ] ) mark [ j - low ] = true ; } for ( int i = low ; i <= high ; i ++ ) { if ( ! mark [ i - low ] ) { allPrimes . insert ( i ) ; } } } int maxPrimeSubarray ( int arr [ ] , int n ) { int current_max = 0 ; int max_so_far = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! allPrimes . count ( arr [ i ] ) ) current_max = 0 ; else { current_max ++ ; max_so_far = max ( current_max , max_so_far ) ; } } return max_so_far ; } int main ( ) { int arr [ ] = { 1 , 2 , 4 , 3 , 29 , 11 , 7 , 8 , 9 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int max_el = * max_element ( arr , arr + n ) ; int min_el = * min_element ( arr , arr + n ) ; primesInRange ( min_el , max_el ) ; cout << maxPrimeSubarray ( arr , n ) ; return 0 ; }