Longest sub | Python3 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 ; Compute all primes less than or equals to sqrt ( high ) using Simple Sieve ; Count the elements in the range [ low , high ] ; Declaring and initializing boolean for the range [ low , high ] to False ; 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 math NEW_LINE allPrimes = set ( ) NEW_LINE def simpleSieve ( limit , prime ) : NEW_LINE INDENT mark = [ False ] * ( limit + 1 ) NEW_LINE for i in range ( 2 , limit + 1 ) : NEW_LINE INDENT if mark [ i ] == False : NEW_LINE INDENT prime . append ( i ) NEW_LINE for j in range ( i , limit + 1 , i ) : NEW_LINE INDENT mark [ j ] = True NEW_LINE DEDENT DEDENT DEDENT DEDENT def primesInRange ( low , high ) : NEW_LINE INDENT limit = math . floor ( math . sqrt ( high ) ) + 1 NEW_LINE prime = [ ] NEW_LINE simpleSieve ( limit , prime ) NEW_LINE n = high - low + 1 NEW_LINE mark = [ False ] * ( n + 1 ) NEW_LINE for i in range ( len ( prime ) ) : NEW_LINE INDENT loLim = low // prime [ i ] NEW_LINE loLim *= prime [ i ] NEW_LINE if loLim < low : NEW_LINE INDENT loLim += prime [ i ] NEW_LINE DEDENT if loLim == prime [ i ] : NEW_LINE INDENT loLim += prime [ i ] NEW_LINE DEDENT for j in range ( loLim , high + 1 , prime [ i ] ) : NEW_LINE INDENT mark [ j - low ] = True NEW_LINE DEDENT DEDENT for i in range ( low , high + 1 ) : NEW_LINE INDENT if not mark [ i - low ] : NEW_LINE INDENT allPrimes . add ( i ) NEW_LINE DEDENT DEDENT DEDENT def maxPrimeSubarray ( arr , n ) : NEW_LINE INDENT current_max = 0 NEW_LINE max_so_far = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if arr [ i ] not in allPrimes : NEW_LINE INDENT current_max = 0 NEW_LINE DEDENT else : NEW_LINE INDENT current_max += 1 NEW_LINE max_so_far = max ( current_max , max_so_far ) NEW_LINE DEDENT DEDENT return max_so_far NEW_LINE DEDENT arr = [ 1 , 2 , 4 , 3 , 29 , 11 , 7 , 8 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE max_el = max ( arr ) NEW_LINE min_el = min ( arr ) NEW_LINE primesInRange ( min_el , max_el ) NEW_LINE print ( maxPrimeSubarray ( arr , n ) ) NEW_LINE