Length of longest increasing prime subsequence from a given array | Javascript 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 ; Initialize all values to true ; Precompute N primes ; Compute optimized LIS having prime numbers in bottom up manner ; Check for LIS and prime ; Return maximum value in lis [ ] ; Given array ; Size of array ; Function Call
let N = 100005 function SieveOfEratosthenes ( prime , p_size ) { prime [ 0 ] = false ; prime [ 1 ] = false ; for ( let p = 2 ; p * p <= p_size ; p ++ ) { if ( prime [ p ] ) { for ( let i = p * 2 ; i <= p_size ; i += p ) prime [ i ] = false ; } } } function LISPrime ( arr , n ) { let lisp = new Array ( n ) ; let prime = new Array ( N + 1 ) ; prime . fill ( true ) ; SieveOfEratosthenes ( prime , N ) ; lisp [ 0 ] = prime [ arr [ 0 ] ] ? 1 : 0 ; for ( let i = 1 ; i < n ; i ++ ) { if ( ! prime [ arr [ i ] ] ) { lisp [ i ] = 0 ; continue ; } lisp [ i ] = 1 ; for ( let j = 0 ; j < i ; j ++ ) { if ( prime [ arr [ j ] ] && arr [ i ] > arr [ j ] && lisp [ i ] < lisp [ j ] + 1 ) { lisp [ i ] = lisp [ j ] + 1 ; } } } return lisp . sort ( ( a , b ) => b - a ) [ 0 ] ; } let arr = [ 1 , 2 , 5 , 3 , 2 , 5 , 1 , 7 ] ; let M = arr . length ; document . write ( LISPrime ( arr , M ) ) ;