Algorithm :

1) Generate all the prime numbers in the range of values of the given array using Sieve Of Eratosthenes.

2) Now make an iteration for ‘arr1’ and check the elements in ‘arr1’ which are prime ...read more

The simplest idea is to consider all subsequences of arr1[] and check if all numbers in this subsequence are prime and appear in arr2[]. Then find the longest length of these subsequences. But the time complexity for this operation will be O(M * (2 ^ N)) where ‘M’ is the length of the first array and ‘N’ is the length of the second array.

We can think of an efficient solution in which first we calculate all the prime numbers from both the arrays and then find the longest common prime subsequence from them using Dynamic Programming. 

For Prime Numbers:

Find all the prime numbers between the minimum element of the array and the maximum element of the array using Sieve Of Eratosthenes algorithm.

For Longest Common Subsequence:

Store the sequence of primes from the arrays arr1[] and arr2[].

Find the LCS of the two sequences of primes.

Approach:

• Generate all the prime numbers in the range of values of the given array using Sieve Of Eratosthenes.
• Now make an iteration for ‘arr1’ and check the elements in ‘arr1’ which are prime and store the elements in an array, say ‘finalA’.
• Now make an iteration for ‘arr2’ and check the elements in ‘arr2’ which are prime and store the elements in an array, say ‘finalB’.
• Now calculate the LCS for the two arrays: ‘finalA’ and ‘finalB’ with the help of ‘lcs()’ function using Dynamic Programming.
• Return the array after calculating the longest common subsequence.

O(N * M), where ‘N’ denotes the length of the array ‘arr1’ and ‘M’ denotes the length of the array ‘arr2’.

As we are maintaining 2 Dimensional auxiliary space i.e. 2D array for calculating the LCS which takes maximum size of (N * M), therefore, overall space complexity will be O(N * M).

O(N * M), where ‘N’ denotes the length of the array ‘arr1’ and ‘M’ denotes the length of the array ‘arr2’.

Finding the longest common subsequence will cost O(N * M) time. And time complexity for calculation prime numbers using Sieve of Eratosthenes is O(N * log(N)). Therefore, time complexity in the worst case will be O(N * M).

/*
	Time Complexity: O(N * M)
	Space Complexity: O(N * M)
	
	Where 'N' is the length of 'arr1',
	'M' is the length of 'arr2'
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

	public static int longestPrimeCommonSubseq(int[] arr1, int[] arr2) {
		boolean[] isPrime = primeNumbers(1000);

		List finala = new ArrayList<>();
		List finalb = new ArrayList<>();

		// Store the elements of arr1 which are prime in finala.
		for (int i = 0; i < arr1.length; i++) {
			if (isPrime[arr1[i]] == true) {
				finala.add(arr1[i]);
			}
		}

		// Store the elements of arr2 which are prime in finalb.
		for (int i = 0; i < arr2.length; i++) {
			if (isPrime[arr2[i]] == true) {
				finalb.add(arr2[i]);
			}
		}

		// Calculating the LCS
		int n = arr1.length;
		int m = arr2.length;

		int dp[][] = new int[505][5050];
		for (int[] row : dp)
			Arrays.fill(row, -1);

		return lcs(finala, finalb, finala.size(), finalb.size(), dp);
	}

	// Function to calculate the LCS
	private static int lcs(List list1, List list2, int m, int n, int[][] dp) {

		// If either of the array is empty.
		if (m == 0 || n == 0) {
			return 0;
		}

		// If we encountered with the recurring subproblem.
		if (dp[m - 1][n - 1] != -1) {
			return dp[m - 1][n - 1];
		}

		// If same elements in both arrays.
		if (list1.get(m - 1).equals(list2.get(n - 1))) {
			dp[m - 1][n - 1] = 1 + lcs(list1, list2, m - 1, n - 1, dp);
		}

		else {
			dp[m - 1][n - 1] = Math.max(lcs(list1, list2, m - 1, n, dp), lcs(list1, list2, m, n - 1, dp));
		}

		return dp[m - 1][n - 1];
	}

	// Function to generate all the possible prime numbers.
	private static boolean[] primeNumbers(int N) {

		// Boolean array to store the prime numbers as true.
		boolean primes[] = new boolean[N + 1];
		Arrays.fill(primes, true);

		// o and 1 are not prime.
		primes[0] = false;
		primes[1] = false;

		int p = 2;

		while (p * p <= N) {
			for (int i = p * p; i <= N; i += p) {

				// Set all prime numbers as false.
				primes[i] = false;
			}

			p = p + 1;
		}

		return primes;
	}

}

'''

    Time Complexity: O(N * M)

    Space Complexity: O(N * M)

    

    Where 'N' is the length of 'arr1',

    'M' is the length of 'arr2'

'''



# Function to calculate the LCS

def lcs(arr1, arr2, m, n, dp):

	

	# If either of the array is empty.

	if (m == 0 or n == 0):

		return 0

		

	# If we encountered with the recurring subproblem. 	

	if(dp[m - 1][n - 1] != -1):

		return dp[m - 1][n - 1]

		

	# If same elements in both arrays.	

	if (arr1[m - 1] == arr2[n - 1]):

		dp[m - 1][n - 1] = 1 + lcs(arr1, arr2, m - 1, n - 1, dp)

	

	else:

		dp[m-1][n-1] = max(lcs(arr1, arr2, m - 1, n, dp), lcs(arr1, arr2, m, n - 1, dp))

	

	return dp[m - 1][n - 1]





# Function to generate all the possible prime numbers.

def primeNumbers(n):

	

	# Boolean array to store the prime numbers as True.

	primes = [True for i in range(n  + 1)]

	

	primes[0] = False

	primes[1] = False

	

	p = 2

	while (p * p <= n):

		for i in range(p * p, n + 1, p):

			# Set all prime numbers as False.

			primes[i] = False

			

		p = p + 1

		

	return primes





def longestPrimeCommonSubseq(arr1, arr2):

	

	isPrime = primeNumbers(1000)

	

	finala = []

	finalb = []

	

	# Store the elements of arr1 which are prime in finala.

	for i in arr1:

		if(isPrime[i] == True):

			finala.append(i)

        

    # Store the elements of arr2 which are prime in finalb.

	for i in arr2:

		if(isPrime[i] == True):

			finalb.append(i)

			

	# Calculating the LCS

	dp = [[-1 for i in range(505)] for i in range(505)]

	return lcs(finala, finalb, len(finala), len(finalb), dp)

/*

    Time Complexity: O(N * M)

    Space Complexity: O(N * M)

    

    Where 'N' is the length of 'arr1',

    'M' is the length of 'arr2'

*/



#include



// Function to calculate the LCS

int lcs(vector arr1,  vector arr2, int m, int n, vector> &dp)

{

    

    // If either of the array is empty.

	if (m == 0 || n == 0)

	{

	    return 0;

	}

	

	// If we encountered with the recurring subproblem. 	

	if(dp[m - 1][n - 1] != -1)

	{

	    return dp[m - 1][n - 1];

	}

	

	// If same elements in both arrays.	

	if (arr1[m - 1] == arr2[n - 1])

	{

	    dp[m - 1][n - 1] = 1 + lcs(arr1, arr2, m - 1, n - 1, dp);

	}



	else

	{

	    dp[m - 1][n - 1] = max(lcs(arr1, arr2, m - 1, n, dp), lcs(arr1, arr2, m, n - 1, dp));

	}

								

    return dp[m - 1][n - 1];

}



// Function to generate all the possible prime numbers.

vector primeNumbers(int n)

{

    

    // Boolean array to store the prime numbers as true.

	vector primes(n + 1, true);

	

	// o and 1 are not prime.

	primes[0] = false;

	primes[1] = false;

	

	int p = 2;

	

	while (p * p <= n)

	{

		for (int i = p * p; i <= n; i += p)

		{

		    

		    // Set all prime numbers as false.

		    primes[i] = false;

		}

		

		p = p + 1;

	}

	

	return primes;

}



int longestPrimeCommonSubseq(vector arr1, vector arr2)

{



	vector isPrime = primeNumbers(1000);



	vector finala;

	vector finalb;



    // Store the elements of arr1 which are prime in finala.

    for(int i = 0; i < arr1.size(); i++)

    {

        if(isPrime[arr1[i]] == true)

        {

            finala.push_back(arr1[i]);

        }

    }

    

    // Store the elements of arr2 which are prime in finalb.

    for(int i = 0; i < arr2.size(); i++)

    {

        if(isPrime[arr2[i]] == true)

        {

            finalb.push_back(arr2[i]);

        }

    }

    

	// Calculating the LCS

	int n = arr1.size();

	int m = arr2.size();



	vector> dp(505, vector(505, -1));



	return lcs(finala, finalb, finala.size(), finalb.size(), dp);

}