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>
Producción:
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.