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(2N)
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 105.
- 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 Eratosthenesvoid 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 Numbersint 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 Codeint 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 approachimport java.util.*;Â
class GFG{Â Â Â Â Â static final int N = 100005;Â
// Function to find the prime numbers// till 10^5 using Sieve of Eratosthenesstatic 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 Numbersstatic 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 Codepublic 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 Eratosthenesdef 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 Numbersdef 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 Codeif __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 approachusing System;using System.Linq;Â
class GFG{Â Â Â Â Â static readonly int N = 100005;Â
// Function to find the prime numbers// till 10^5 using Sieve of Eratosthenesstatic 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 Numbersstatic 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 Codepublic 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 Eratosthenesfunction 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 Numbersfunction 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:Â
4
Time Complexity: O(N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
