Length of longest increasing prime subsequence from a given array

0 0 7 minutes read

Given an array arr[] consisting of N positive integers, the task is to find the length of the longest increasing subsequence consisting of Prime Numbers in the given array.

Examples:

Input: arr[] = {1, 2, 5, 3, 2, 5, 1, 7}
Output: 4
Explanation:
The Longest Increasing Prime Subsequence is {2, 3, 5, 7}.
Therefore, the answer is 4.

Input: arr[] = {6, 11, 7, 13, 9, 25}
Output: 2
Explanation:
The Longest Increasing Prime Subsequence is {11, 13} and {7, 13}.
Therefore, the answer is 2.

Naive Approach: The simplest approach is to generate all possible subsequence of the given array and print the length of the longest subsequence consisting of prime numbers in increasing order.
Time Complexity: O(2^N)
Auxiliary Space: O(N)

Efficient Approach: The idea is to use the Dynamic Programming approach to optimize the above approach. This problem is a basic variation of the Longest Increasing Subsequence (LIS) problem. Below are the steps:

Initialize an auxiliary array dp[] of size N such that dp[i] will store the length of LIS of prime numbers ending at index i.
Below is the recurrence relation for finding the longest increasing Prime Numbers:

If arr[i] is prime then
dp[i] = 1 + max(dp[j], for j belongs (0, i – 1)), where 0 < j < i and arr[j] < arr[i];
dp[i] = 1, if no such j exists
else if arr[i] is non-prime then
dp[i] = 0

Using Sieve of Eratosthenes store all the prime numbers to till 10⁵.
Iterate a two nested loop over the given array and update the array dp[] according to the above recurrence relation.
After all the above steps, the maximum element in the array dp[] is the length of the longest increasing subsequence of Prime Numbers in the given array.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define N 100005
 
// Function to find the prime numbers
// till 10^5 using Sieve of Eratosthenes
void SieveOfEratosthenes(bool prime[],
                         int p_size)
{
    // False here indicates
    // that it is not prime
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p * p <= p_size; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p]) {
 
            // Update all multiples of p,
            // set them to non-prime
            for (int i = p * 2;
                 i <= p_size; i += p)
                prime[i] = false;
        }
    }
}
 
// Function which computes the length
// of the LIS of Prime Numbers
int LISPrime(int arr[], int n)
{
    // Create an array of size n
    int lisp[n];
 
    // Create boolean array to
    // mark prime numbers
    bool prime[N + 1];
 
    // Initialize all values to true
    memset(prime, true, sizeof(prime));
 
    // Precompute N primes
    SieveOfEratosthenes(prime, N);
 
    lisp[0] = prime[arr[0]] ? 1 : 0;
 
    // Compute optimized LIS having
    // prime numbers in bottom up manner
    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++) {
 
            // Check for LIS and prime
            if (prime[arr[j]]
                && arr[i] > arr[j]
                && lisp[i] < lisp[j] + 1) {
                lisp[i] = lisp[j] + 1;
            }
        }
    }
 
    // Return maximum value in lis[]
    return *max_element(lisp, lisp + n);
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 1, 2, 5, 3, 2, 5, 1, 7 };
 
    // Size of array
    int M = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << LISPrime(arr, M);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static final int N = 100005;
 
// Function to find the prime numbers
// till 10^5 using Sieve of Eratosthenes
static void SieveOfEratosthenes(boolean prime[],
                                int p_size)
{
     
    // False here indicates
    // that it is not prime
    prime[0] = false;
    prime[1] = false;
 
    for(int p = 2; p * p <= p_size; p++) 
    {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p]) 
        {
 
            // Update all multiples of p,
            // set them to non-prime
            for(int i = p * 2;
                    i <= p_size;
                    i += p)
                prime[i] = false;
        }
    }
}
 
// Function which computes the length
// of the LIS of Prime Numbers
static int LISPrime(int arr[], int n)
{
     
    // Create an array of size n
    int []lisp = new int[n];
 
    // Create boolean array to
    // mark prime numbers
    boolean []prime = new boolean[N + 1];
 
    // Initialize all values to true
    for(int i = 0; i < prime.length; i++)
        prime[i] = true;
 
    // Precompute N primes
    SieveOfEratosthenes(prime, N);
 
    lisp[0] = prime[arr[0]] ? 1 : 0;
 
    // Compute optimized LIS having
    // prime numbers in bottom up manner
    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++) 
        {
             
            // Check for LIS and prime
            if (prime[arr[j]] && 
                arr[i] > arr[j] && 
               lisp[i] < lisp[j] + 1) 
            {
                lisp[i] = lisp[j] + 1;
            }
        }
    }
 
    // Return maximum value in lis[]
    return Arrays.stream(lisp).max().getAsInt();
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array
    int arr[] = { 1, 2, 5, 3, 2, 5, 1, 7 };
 
    // Size of array
    int M = arr.length;
 
    // Function call
    System.out.print(LISPrime(arr, M));
}
}
 
// This code is contributed by Amit Katiyar

Python3

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

C#

// C# program for the above approach
using System;
using System.Linq;
 
class GFG{
     
static readonly int N = 100005;
 
// Function to find the prime numbers
// till 10^5 using Sieve of Eratosthenes
static void SieveOfEratosthenes(bool []prime,
                                int p_size)
{
     
    // False here indicates
    // that it is not prime
    prime[0] = false;
    prime[1] = false;
 
    for(int p = 2; p * p <= p_size; p++) 
    {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p]) 
        {
 
            // Update all multiples of p,
            // set them to non-prime
            for(int i = p * 2;
                    i <= p_size;
                    i += p)
                prime[i] = false;
        }
    }
}
 
// Function which computes the length
// of the LIS of Prime Numbers
static int LISPrime(int []arr, int n)
{
     
    // Create an array of size n
    int []lisp = new int[n];
 
    // Create bool array to
    // mark prime numbers
    bool []prime = new bool[N + 1];
 
    // Initialize all values to true
    for(int i = 0; i < prime.Length; i++)
        prime[i] = true;
 
    // Precompute N primes
    SieveOfEratosthenes(prime, N);
 
    lisp[0] = prime[arr[0]] ? 1 : 0;
 
    // Compute optimized LIS having
    // prime numbers in bottom up manner
    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++) 
        {
             
            // Check for LIS and prime
            if (prime[arr[j]] && 
                arr[i] > arr[j] && 
               lisp[i] < lisp[j] + 1) 
            {
                lisp[i] = lisp[j] + 1;
            }
        }
    }
 
    // Return maximum value in lis[]
    return lisp.Max();
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array
    int []arr = { 1, 2, 5, 3, 2, 5, 1, 7 };
 
    // Size of array
    int M = arr.Length;
 
    // Function call
    Console.Write(LISPrime(arr, M));
}
}
 
// This code is contributed by Amit Katiyar 

Javascript

<script>
 
// Javascript program for the above approach
 
let N = 100005
 
// Function to find the prime numbers
// till 10^5 using Sieve of Eratosthenes
function SieveOfEratosthenes(prime, p_size)
{
    // False here indicates
    // that it is not prime
    prime[0] = false;
    prime[1] = false;
 
    for (let p = 2; p * p <= p_size; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p]) {
 
            // Update all multiples of p,
            // set them to non-prime
            for (let i = p * 2;
                 i <= p_size; i += p)
                prime[i] = false;
        }
    }
}
 
// Function which computes the length
// of the LIS of Prime Numbers
function LISPrime(arr, n)
{
    // Create an array of size n
    let lisp = new Array(n);
 
    // Create boolean array to
    // mark prime numbers
    let prime = new Array(N + 1);
 
    // Initialize all values to true
    prime.fill(true);
 
    // Precompute N primes
    SieveOfEratosthenes(prime, N);
 
    lisp[0] = prime[arr[0]] ? 1 : 0;
 
    // Compute optimized LIS having
    // prime numbers in bottom up manner
    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++) {
 
            // Check for LIS and prime
            if (prime[arr[j]]
                && arr[i] > arr[j]
                && lisp[i] < lisp[j] + 1) {
                lisp[i] = lisp[j] + 1;
            }
        }
    }
 
    // Return maximum value in lis[]
    return lisp.sort((a, b) => b - a)[0];
}
 
// Driver Code
 
    // Given array
    let arr = [ 1, 2, 5, 3, 2, 5, 1, 7 ];
 
    // Size of array
    let M = arr.length;
 
    // Function Call
    document.write(LISPrime(arr, M));
 
// This code is contributed by gfgking
 
</script>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!