Dado un arreglo arr[] de N enteros, la tarea es encontrar el subarreglo más largo donde todos los números en ese subarreglo sean primos.
Ejemplos:
Entrada: arr[] = {3, 5, 2, 66, 7, 11, 8}
Salida: 3
Explicación:
La secuencia máxima de números primos contiguos es {2, 3, 5}Entrada: arr[] = {1, 2, 11, 32, 8, 9}
Salida: 2
Explicación:
La secuencia máxima de números primos contiguos es {2, 11}
Enfoque:
Para elementos de la array en orden de 10 6 , hemos discutido un enfoque en este artículo.
Para los elementos del arreglo en orden de 10 9 , la idea es usar Tamiz Segmentado para encontrar los Números Primos que valgan hasta 10 9 .
Pasos :
- Encuentre los números primos entre el rango del elemento mínimo y el elemento máximo de la array usando el enfoque discutido en este artículo.
- Después de calcular los números primos entre el rango. El subarreglo más largo con números primos se puede calcular usando el algoritmo de Kadane . Los siguientes son los pasos:
- Recorra la array dada arr[] con dos variables llamadas current_max y max_so_far .
- Si se encuentra un número primo , aumente current_max y compárelo con max_so_far .
- Si current_max es mayor que max_so_far , actualice max_so_far a current_max .
- Si algún elemento no es un elemento principal, restablezca current_max a 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find longest subarray // of prime numbers #include <bits/stdc++.h> using namespace std; // To store the prime numbers unordered_set<int> allPrimes; // Function that find prime numbers // till limit void simpleSieve(int limit, vector<int>& prime) { bool mark[limit + 1]; memset(mark, false, sizeof(mark)); // Find primes using // Sieve of Eratosthenes for (int i = 2; i <= limit; ++i) { if (mark[i] == false) { prime.push_back(i); for (int j = i; j <= limit; j += i) { mark[j] = true; } } } } // Function that finds all prime // numbers in given range using // Segmented Sieve void primesInRange(int low, int high) { // Find the limit int limit = floor(sqrt(high)) + 1; // To store the prime numbers vector<int> prime; // Comput all primes less than // or equals to sqrt(high) // using Simple Sieve simpleSieve(limit, prime); // Count the elements in the // range [low, high] int n = high - low + 1; // Declaring boolean for the // range [low, high] bool mark[n + 1]; // Initialise bool[] to false memset(mark, false, sizeof(mark)); // Traverse the prime numbers till // limit for (int i = 0; i < prime.size(); i++) { int loLim = floor(low / prime[i]); loLim *= prime[i]; // Find the minimum number in // [low..high] that is a // multiple of prime[i] if (loLim < low) { loLim += prime[i]; } if (loLim == prime[i]) { loLim += prime[i]; } // Mark the multiples of prime[i] // in [low, high] as true for (int j = loLim; j <= high; j += prime[i]) mark[j - low] = true; } // Element which are not marked in // range are Prime for (int i = low; i <= high; i++) { if (!mark[i - low]) { allPrimes.insert(i); } } } // Function that finds longest subarray // of prime numbers int maxPrimeSubarray(int arr[], int n) { int current_max = 0; int max_so_far = 0; for (int i = 0; i < n; i++) { // If element is Non-prime then // updated current_max to 0 if (!allPrimes.count(arr[i])) current_max = 0; // If element is prime, then // update current_max and // max_so_far else { current_max++; max_so_far = max(current_max, max_so_far); } } // Return the count of longest // subarray return max_so_far; } // Driver Code int main() { int arr[] = { 1, 2, 4, 3, 29, 11, 7, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); // Find minimum and maximum element int max_el = *max_element(arr, arr + n); int min_el = *min_element(arr, arr + n); // Find prime in the range // [min_el, max_el] primesInRange(min_el, max_el); // Function call cout << maxPrimeSubarray(arr, n); return 0; }
Java
// Java program to find longest subarray // of prime numbers import java.util.*; import java.lang.*; import java.io.*; class GFG{ // To store the prime numbers static Set<Integer> allPrimes = new HashSet<>(); // Function that find prime numbers // till limit static void simpleSieve(int limit, ArrayList<Integer> prime) { boolean []mark = new boolean[limit + 1]; // Find primes using // Sieve of Eratosthenes for(int i = 2; i <= limit; ++i) { if (mark[i] == false) { prime.add(i); for(int j = i; j <= limit; j += i) { mark[j] = true; } } } } // Function that finds all prime // numbers in given range using // Segmented Sieve static void primesInRange(int low, int high) { // Find the limit int limit = (int)Math.floor(Math.sqrt(high)) + 1; // To store the prime numbers ArrayList<Integer> prime = new ArrayList<>(); // Comput all primes less than // or equals to sqrt(high) // using Simple Sieve simpleSieve(limit, prime); // Count the elements in the // range [low, high] int n = high - low + 1; // Declaring boolean for the // range [low, high] boolean []mark = new boolean[n + 1]; // Traverse the prime numbers till // limit for(int i = 0; i < prime.size(); i++) { int loLim = (int)Math.floor((double)low / (int)prime.get(i)); loLim *= (int)prime.get(i); // Find the minimum number in // [low..high] that is a // multiple of prime[i] if (loLim < low) { loLim += (int)prime.get(i); } if (loLim == (int)prime.get(i)) { loLim += (int)prime.get(i); } // Mark the multiples of prime[i] // in [low, high] as true for(int j = loLim; j <= high; j += (int)prime.get(i)) mark[j - low] = true; } // Element which are not marked in // range are Prime for(int i = low; i <= high; i++) { if (!mark[i - low]) { allPrimes.add(i); } } } // Function that finds longest subarray // of prime numbers static int maxPrimeSubarray(int []arr, int n) { int current_max = 0; int max_so_far = 0; for(int i = 0; i < n; i++) { // If element is Non-prime then // updated current_max to 0 if (!allPrimes.contains(arr[i])) current_max = 0; // If element is prime, then // update current_max and // max_so_far else { current_max++; max_so_far = Math.max(current_max, max_so_far); } } // Return the count of longest // subarray return max_so_far; } // Driver code public static void main(String[] args) { int []arr = { 1, 2, 4, 3, 29, 11, 7, 8, 9 }; int n = arr.length; // Find minimum and maximum element int max_el = Integer.MIN_VALUE; int min_el = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if (arr[i] < min_el) { min_el = arr[i]; } if (arr[i] > max_el) { max_el = arr[i]; } } // Find prime in the range // [min_el, max_el] primesInRange(min_el, max_el); // Function call System.out.print(maxPrimeSubarray(arr, n)); } } // This code is contributed by offbeat
Python3
# Python3 program to find longest subarray # of prime numbers import math # To store the prime numbers allPrimes = set() # Function that find prime numbers # till limit def simpleSieve(limit, prime): mark = [False] * (limit + 1) # Find primes using # Sieve of Eratosthenes for i in range(2, limit + 1): if mark[i] == False: prime.append(i) for j in range(i, limit + 1, i): mark[j] = True # Function that finds all prime # numbers in given range using # Segmented Sieve def primesInRange(low, high): # Find the limit limit = math.floor(math.sqrt(high)) + 1 # To store the prime numbers prime = [] # Compute all primes less than # or equals to sqrt(high) # using Simple Sieve simpleSieve(limit, prime) # Count the elements in the # range [low, high] n = high - low + 1 # Declaring and initializing boolean # for the range[low,high] to False mark = [False] * (n + 1) # Traverse the prime numbers till # limit for i in range(len(prime)): loLim = low // prime[i] loLim *= prime[i] # Find the minimum number in # [low..high] that is a # multiple of prime[i] if loLim < low: loLim += prime[i] if loLim == prime[i]: loLim += prime[i] # Mark the multiples of prime[i] # in [low, high] as true for j in range(loLim, high + 1, prime[i]): mark[j - low] = True # Element which are not marked in # range are Prime for i in range(low, high + 1): if not mark[i - low]: allPrimes.add(i) # Function that finds longest subarray # of prime numbers def maxPrimeSubarray(arr, n): current_max = 0 max_so_far = 0 for i in range(n): # If element is Non-prime then # updated current_max to 0 if arr[i] not in allPrimes: current_max = 0 # If element is prime, then # update current_max and # max_so_far else: current_max += 1 max_so_far = max(current_max, max_so_far) # Return the count of longest # subarray return max_so_far # Driver Code arr = [ 1, 2, 4, 3, 29, 11, 7, 8, 9 ] n = len(arr) # Find minimum and maximum element max_el = max(arr) min_el = min(arr) # Find prime in the range # [min_el, max_el] primesInRange(min_el, max_el) # Function call print(maxPrimeSubarray(arr, n)) # This code is contributed by Shivam Singh
C#
// C# program to find longest subarray // of prime numbers using System; using System.Collections; using System.Collections.Generic; class GFG{ // To store the prime numbers static HashSet<int> allPrimes = new HashSet<int>(); // Function that find prime numbers // till limit static void simpleSieve(int limit, ref ArrayList prime) { bool []mark = new bool[limit + 1]; Array.Fill(mark, false); // Find primes using // Sieve of Eratosthenes for(int i = 2; i <= limit; ++i) { if (mark[i] == false) { prime.Add(i); for(int j = i; j <= limit; j += i) { mark[j] = true; } } } } // Function that finds all prime // numbers in given range using // Segmented Sieve static void primesInRange(int low, int high) { // Find the limit int limit = (int)Math.Floor(Math.Sqrt(high)) + 1; // To store the prime numbers ArrayList prime = new ArrayList(); // Comput all primes less than // or equals to sqrt(high) // using Simple Sieve simpleSieve(limit, ref prime); // Count the elements in the // range [low, high] int n = high - low + 1; // Declaring boolean for the // range [low, high] bool []mark = new bool[n + 1]; // Initialise bool[] to false Array.Fill(mark, false); // Traverse the prime numbers till // limit for(int i = 0; i < prime.Count; i++) { int loLim = (int)Math.Floor((double)low / (int)prime[i]); loLim *= (int)prime[i]; // Find the minimum number in // [low..high] that is a // multiple of prime[i] if (loLim < low) { loLim += (int)prime[i]; } if (loLim == (int)prime[i]) { loLim += (int)prime[i]; } // Mark the multiples of prime[i] // in [low, high] as true for(int j = loLim; j <= high; j += (int)prime[i]) mark[j - low] = true; } // Element which are not marked in // range are Prime for(int i = low; i <= high; i++) { if (!mark[i - low]) { allPrimes.Add(i); } } } // Function that finds longest subarray // of prime numbers static int maxPrimeSubarray(int []arr, int n) { int current_max = 0; int max_so_far = 0; for(int i = 0; i < n; i++) { // If element is Non-prime then // updated current_max to 0 if (!allPrimes.Contains(arr[i])) current_max = 0; // If element is prime, then // update current_max and // max_so_far else { current_max++; max_so_far = Math.Max(current_max, max_so_far); } } // Return the count of longest // subarray return max_so_far; } // Driver code public static void Main(string[] args) { int []arr = { 1, 2, 4, 3, 29, 11, 7, 8, 9 }; int n = arr.Length; // Find minimum and maximum element int max_el = Int32.MinValue; int min_el = Int32.MaxValue; for(int i = 0; i < n; i++) { if (arr[i] < min_el) { min_el = arr[i]; } if (arr[i] > max_el) { max_el = arr[i]; } } // Find prime in the range // [min_el, max_el] primesInRange(min_el, max_el); // Function call Console.Write(maxPrimeSubarray(arr, n)); } } // This code is contributed by rutvik_56
Javascript
<script> // Javascript program to find longest subarray // of prime numbers // To store the prime numbers let allPrimes = new Set(); // Function that find prime numbers // till limit function simpleSieve(limit, prime) { let mark = Array.from({length: limit + 1}, (_, i) => 0); // Find primes using // Sieve of Eratosthenes for(let i = 2; i <= limit; ++i) { if (mark[i] == false) { prime.push(i); for(let j = i; j <= limit; j += i) { mark[j] = true; } } } } // Function that finds all prime // numbers in given range using // Segmented Sieve function primesInRange(low, high) { // Find the limit let limit = Math.floor(Math.sqrt(high)) + 1; // To store the prime numbers let prime = []; // Comput all primes less than // or equals to sqrt(high) // using Simple Sieve simpleSieve(limit, prime); // Count the elements in the // range [low, high] let n = high - low + 1; // Declaring boolean for the // range [low, high] let mark = Array.from({length: n + 1}, (_, i) => 0); // Traverse the prime numbers till // limit for(let i = 0; i < prime.length; i++) { let loLim = Math.floor(low / prime[i]); loLim *= prime[i]; // Find the minimum number in // [low..high] that is a // multiple of prime[i] if (loLim < low) { loLim += prime[i]; } if (loLim == prime[i]) { loLim += prime[i]; } // Mark the multiples of prime[i] // in [low, high] as true for(let j = loLim; j <= high; j += prime[i]) mark[j - low] = true; } // Element which are not marked in // range are Prime for(let i = low; i <= high; i++) { if (!mark[i - low]) { allPrimes.add(i); } } } // Function that finds longest subarray // of prime numbers function maxPrimeSubarray(arr, n) { let current_max = 0; let max_so_far = 0; for(let i = 0; i < n; i++) { // If element is Non-prime then // updated current_max to 0 if (!allPrimes.has(arr[i])) current_max = 0; // If element is prime, then // update current_max and // max_so_far else { current_max++; max_so_far = Math.max(current_max, max_so_far); } } // Return the count of longest // subarray return max_so_far; } // Driver code let arr = [ 1, 2, 4, 3, 29, 11, 7, 8, 9 ]; let n = arr.length; // Find minimum and maximum element let max_el = Number.MIN_VALUE; let min_el = Number.MAX_VALUE; for(let i = 0; i < n; i++) { if (arr[i] < min_el) { min_el = arr[i]; } if (arr[i] > max_el) { max_el = arr[i]; } } // Find prime in the range // [min_el, max_el] primesInRange(min_el, max_el); // Function call document.write(maxPrimeSubarray(arr, n)); </script>
4
Complejidad de tiempo: O(N), donde N es la longitud de la array.
Espacio Auxiliar: O(N), donde N es la longitud del arreglo.