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 approachlet 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!
