Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la longitud de la subsecuencia creciente más larga que consta de números primos en la array dada.
Ejemplos:
Entrada: arr[] = {1, 2, 5, 3, 2, 5, 1, 7}
Salida: 4
Explicación:
La subsecuencia prima creciente más larga es {2, 3, 5, 7}.
Por lo tanto, la respuesta es 4.Entrada: arr[] = {6, 11, 7, 13, 9, 25}
Salida: 2
Explicación:
La subsecuencia prima creciente más larga es {11, 13} y {7, 13}.
Por lo tanto, la respuesta es 2.
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles de la array dada e imprimir la longitud de la subsecuencia más larga que consta de números primos en orden creciente.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es utilizar el enfoque de programación dinámica para optimizar el enfoque anterior. Este problema es una variación básica del problema de la subsecuencia creciente más larga (LIS). A continuación se muestran los pasos:
- Inicialice una array auxiliar dp[] de tamaño N tal que dp[i] almacenará la longitud de LIS de números primos que terminan en el índice i .
- A continuación se muestra la relación de recurrencia para encontrar los números primos crecientes más largos:
Si arr[i] es primo, entonces
dp[i] = 1 + max(dp[j], porque j pertenece a (0, i – 1)), donde 0 < j < i y arr[j] < arr[i] ;
dp[i] = 1, si no existe tal j,
si arr[i] no es primo entonces
dp[i] = 0
- Usando el tamiz de Eratóstenes , almacene todos los números primos hasta el 10 5 .
- Itere un ciclo anidado de dos sobre la array dada y actualice la array dp[] de acuerdo con la relación de recurrencia anterior.
- Después de todos los pasos anteriores, el elemento máximo en la array dp[] es la longitud de la subsecuencia creciente más larga de números primos en la array dada.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
4
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA