Length of longest increasing prime subsequence from a given array | Python3 program for the above approach ; Function to find the prime numbers till 10 ^ 5 using Sieve of Eratosthenes ; False here indicates that it is not prime ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p , set them to non - prime ; Function which computes the length of the LIS of Prime Numbers ; Create an array of size n ; Create boolean array to mark prime numbers ; Precompute N primes ; Compute optimized LIS having prime numbers in bottom up manner ; check for LIS and prime ; Return maximum value in lis [ ] ; Driver Code ; Given array ; Size of array ; Function Call
N = 100005 NEW_LINE def SieveOfEratosthenes ( prime , p_size ) : NEW_LINE INDENT prime [ 0 ] = False NEW_LINE prime [ 1 ] = False NEW_LINE p = 2 NEW_LINE while p * p <= p_size : NEW_LINE INDENT if ( prime [ p ] ) : NEW_LINE for i in range ( p * 2 , p_size + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE p += 1 NEW_LINE DEDENT DEDENT DEDENT def LISPrime ( arr , n ) : NEW_LINE INDENT lisp = [ 0 ] * n NEW_LINE prime = [ True ] * ( N + 1 ) NEW_LINE SieveOfEratosthenes ( prime , N ) NEW_LINE if prime [ arr [ 0 ] ] : NEW_LINE INDENT lisp [ 0 ] = 1 NEW_LINE else : NEW_LINE lisp [ 0 ] = 0 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( not prime [ arr [ i ] ] ) : NEW_LINE lisp [ i ] = 0 NEW_LINE continue NEW_LINE lisp [ i ] = 1 NEW_LINE for j in range ( i ) : NEW_LINE INDENT if ( prime [ arr [ j ] ] and arr [ i ] > arr [ j ] and lisp [ i ] < lisp [ j ] + 1 ) : NEW_LINE lisp [ i ] = lisp [ j ] + 1 NEW_LINE return max ( lisp ) NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 5 , 3 , 2 , 5 , 1 , 7 ] NEW_LINE M = len ( arr ) NEW_LINE print ( LISPrime ( arr , M ) ) NEW_LINE DEDENT