Length of longest increasing prime subsequence from a given array | Java 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 [ ] ; Driver Code ; Given array ; Size of array ; Function call
import java . util . * ; class GFG { static final int N = 100005 ; static void SieveOfEratosthenes ( boolean prime [ ] , int p_size ) { prime [ 0 ] = false ; prime [ 1 ] = false ; for ( int p = 2 ; p * p <= p_size ; p ++ ) { if ( prime [ p ] ) { for ( int i = p * 2 ; i <= p_size ; i += p ) prime [ i ] = false ; } } } static int LISPrime ( int arr [ ] , int n ) { int [ ] lisp = new int [ n ] ; boolean [ ] prime = new boolean [ N + 1 ] ; for ( int i = 0 ; i < prime . length ; i ++ ) prime [ i ] = true ; SieveOfEratosthenes ( prime , N ) ; lisp [ 0 ] = prime [ arr [ 0 ] ] ? 1 : 0 ; for ( int i = 1 ; i < n ; i ++ ) { if ( ! prime [ arr [ i ] ] ) { lisp [ i ] = 0 ; continue ; } lisp [ i ] = 1 ; for ( int j = 0 ; j < i ; j ++ ) { if ( prime [ arr [ j ] ] && arr [ i ] > arr [ j ] && lisp [ i ] < lisp [ j ] + 1 ) { lisp [ i ] = lisp [ j ] + 1 ; } } } return Arrays . stream ( lisp ) . max ( ) . getAsInt ( ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 5 , 3 , 2 , 5 , 1 , 7 } ; int M = arr . length ; System . out . print ( LISPrime ( arr , M ) ) ; } }