Número primo más cercano en el arreglo de cada elemento del arreglo

Dada una array de enteros arr[] que consta de N enteros, la tarea es encontrar el número primo más cercano en la array para cada elemento de la array. Si la array no contiene ningún número primo, imprima -1

Ejemplos: 

Entrada: arr[] = {1, 2, 3, 1, 6} 
Salida: 2 2 3 3 3 
Explicación: 
Para el subarreglo {1, 2 }, el número primo más cercano es 2. 
Para el subarreglo { 3 , 1, 6}, el número primo más cercano es 3.

Entrada: arr[] = {8, 7, 12, 15, 3, 11} 
Salida: 7 7 7 3 3 11 
Explicación: 
Para el subarreglo {8, 7 , 12}, el número primo más cercano es 7. 
Para el subarreglo {15, 3 }, el número primo más cercano es 3. 
Para el subarreglo {11} , el número primo más cercano es el mismo 11. 
  

Enfoque: 
siga los pasos a continuación para resolver el problema:  

  • Encuentre el elemento máximo maxm en la array.
  • Calcule y almacene todos los números primos hasta maxm usando Sieve of Eratosthenes
  • Recorre la array y almacena los índices de los números primos.
  • Si no hay números primos en la array, imprima -1 para todos los índices.
  • Señale curr al primer índice que consiste en un número primo.
  • Para cada índice hasta curr , imprima arr[primes[curr]] como el número primo más cercano.
  • Para índices superiores a curr , compare la distancia con primos[curr] y primes[curr + 1]. Si primes[curr] está más cerca, imprime arr[primes[curr]] . De lo contrario, incremente curr nad print arr[primes[curr]] .
  • Si curr es el último número primo de la array, imprime arr[primos[curr]] para todos los índices en adelante.

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ program to find nearest
// prime number in the array
// for all array elements
#include <bits/stdc++.h>
using namespace std;
 
#define max 10000000
 
// Create a boolean array and set all
// entries it as false. A value in
// prime[i] will be true if i is not a
// prime, else false
bool prime[max] = { false };
 
// Sieve of Eratosthenes function
void SieveOfEratosthenes(int maxm)
{
    prime[0] = prime[1] = true;
    for (int i = 2; i * i <= maxm; i++) {
        // Update all multiples of i greater
        // than or equal to the square of it
        // numbers which are multiple of i and are
        // less than i^2 are already been marked.
        if (!prime[i]) {
            for (int j = i * i; j <= maxm; j += i) {
                prime[j] = true;
            }
        }
    }
}
// Function to find nearest
// prime number for all elements
void print_nearest_prime(int arr[], int N)
{
    int maxm = *max_element(arr, arr + N);
    // Compute and store all prime
    // numbers up to maxm
    SieveOfEratosthenes(maxm);
 
    vector<int> primes;
    for (int i = 0; i < N; i++) {
        // Store the indices of
        // all primes
        if (!prime[arr[i]])
            primes.push_back(i);
    }
 
    // If no primes are present
    // in the array
    if (primes.size() == 0) {
        for (int i = 0; i < N; i++) {
            cout << -1 << " ";
        }
 
        return;
    }
 
    // Store the current prime
    int curr = 0;
    for (int i = 0; i < N; i++) {
        // If the no further
        // primes exist in the array
        if (curr == primes.size() - 1
            // For all indices less than
            // that of the current prime
            || i <= primes[curr]) {
            cout << arr[primes[curr]] << " ";
            continue;
        }
 
        // If the current prime is
        // nearer
        if (abs(primes[curr] - i)
            < abs(primes[curr + 1] - i)) {
            cout << arr[primes[curr]] << " ";
        }
        // If the next prime is nearer
        else {
            // Make the next prime
            // as the current
            curr++;
            cout << arr[primes[curr]] << " ";
        }
    }
}
// Driver Program
int main()
{
    int N = 6;
    int arr[] = { 8, 7, 12, 15, 3, 11 };
    print_nearest_prime(arr, N);
    return 0;
}

Java

// Java program to find nearest
// prime number in the array
// for all array elements
import java.util.*;
 
class GFG{
 
static final int max = 10000000;
 
// Create a boolean array and set all
// entries it as false. A value in
// prime[i] will be true if i is not a
// prime, else false
static boolean []prime = new boolean[max];
 
// Sieve of Eratosthenes function
static void SieveOfEratosthenes(int maxm)
{
    prime[0] = prime[1] = true;
     
    for(int i = 2; i * i <= maxm; i++)
    {
         
       // Update all multiples of i greater
       // than or equal to the square of it
       // numbers which are multiple of i
       // and are less than i^2 are already
       // been marked.
       if (!prime[i])
       {
           for(int j = i * i;
                   j <= maxm; j += i)
           {
              prime[j] = true;
           }
       }
    }
}
 
// Function to find nearest
// prime number for all elements
static void print_nearest_prime(int arr[], int N)
{
    int maxm = Arrays.stream(arr).max().getAsInt();
     
    // Compute and store all prime
    // numbers up to maxm
    SieveOfEratosthenes(maxm);
 
    Vector<Integer> primes = new Vector<Integer>();
     
    for(int i = 0; i < N; i++)
    {
         
       // Store the indices of
       // all primes
       if (!prime[arr[i]])
           primes.add(i);
    }
 
    // If no primes are present
    // in the array
    if (primes.size() == 0)
    {
        for(int i = 0; i < N; i++)
        {
           System.out.print(-1 + " ");
        }
        return;
    }
 
    // Store the current prime
    int curr = 0;
    for(int i = 0; i < N; i++)
    {
         
       // If the no further
       // primes exist in the array
       if (curr == primes.size() - 1 ||
        
           // For all indices less than
           // that of the current prime
           i <= primes.get(curr))
       {
           System.out.print(
               arr[primes.get(curr)] + " ");
           continue;
       }
        
       // If the current prime is
       // nearer
       if (Math.abs(primes.get(curr) - i) <
           Math.abs(primes.get(curr + 1) - i))
       {
           System.out.print(
               arr[primes.get(curr)] + " ");
       }
        
       // If the next prime is nearer
       else
       {
            
           // Make the next prime
           // as the current
           curr++;
           System.out.print(
               arr[primes.get(curr)] + " ");
       }
    }
}
 
// Driver code
public static void main(String[] args)
{
    int N = 6;
    int arr[] = { 8, 7, 12, 15, 3, 11 };
     
    print_nearest_prime(arr, N);
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to find nearest
# prime number in the array
# for all array elements
maxi = 10000000
 
# Create a boolean array and set all
# entries it as false. A value in
# prime[i] will be true if i is not a
# prime, else false
prime = [False] * (maxi)
 
# Sieve of Eratosthenes function
def SieveOfEratosthenes(maxm):
     
    prime[0] = prime[1] = True
    for i in range(2, maxm + 1):
        if i * i > maxm:
            break
             
        # Update all multiples of i greater
        # than or equal to the square of it
        # numbers which are multiple of i and are
        # less than i^2 are already been marked.
        if (not prime[i]):
            for j in range(i * i, maxm + 1, i):
                prime[j] = True
 
# Function to find nearest
# prime number for all elements
def print_nearest_prime(arr, N):
 
    maxm = max(arr)
     
    # Compute and store all prime
    # numbers up to maxm
    SieveOfEratosthenes(maxm)
 
    primes = []
    for i in range(N):
         
        # Store the indices of
        # all primes
        if (not prime[arr[i]]):
            primes.append(i)
 
    # If no primes are present
    # in the array
    if len(primes) == 0:
        for i in range(N):
            print(-1, end = " ")
        return
         
    # Store the current prime
    curr = 0
    for i in range(N):
         
        # If the no further primes
        # exist in the array
        if (curr == len(primes) - 1 or
         
            # For all indices less than
            # that of the current prime
            i <= primes[curr]):
            print(arr[primes[curr]], end = " ")
            continue
 
        # If the current prime is
        # nearer
        if (abs(primes[curr] - i) <
            abs(primes[curr + 1] - i)):
            print(arr[primes[curr]], end = " ")
             
        # If the next prime is nearer
        else:
             
            # Make the next prime
            # as the current
            curr += 1
            print(arr[primes[curr]], end = " ")
             
# Driver code
if __name__ == '__main__':
     
    N = 6
    arr = [ 8, 7, 12, 15, 3, 11 ]
     
    print_nearest_prime(arr, N)
 
# This code is contributed by mohit kumar 29

C#

// C# program to find nearest
// prime number in the array
// for all array elements
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG{
 
static readonly int max = 10000000;
 
// Create a bool array and set all
// entries it as false. A value in
// prime[i] will be true if i is not a
// prime, else false
static bool []prime = new bool[max];
 
// Sieve of Eratosthenes function
static void SieveOfEratosthenes(int maxm)
{
    prime[0] = prime[1] = true;
     
    for(int i = 2; i * i <= maxm; i++)
    {
     
        // Update all multiples of i greater
        // than or equal to the square of it
        // numbers which are multiple of i
        // and are less than i^2 are already
        // been marked.
        if (!prime[i])
        {
            for(int j = i * i;
                    j <= maxm; j += i)
            {
                prime[j] = true;
            }
        }
    }
}
 
// Function to find nearest
// prime number for all elements
static void print_nearest_prime(int []arr,
                                int N)
{
    int maxm = arr.Max();
     
    // Compute and store all prime
    // numbers up to maxm
    SieveOfEratosthenes(maxm);
 
    List<int> primes = new List<int>();
     
    for(int i = 0; i < N; i++)
    {
         
        // Store the indices of
        // all primes
        if (!prime[arr[i]])
            primes.Add(i);
    }
     
    // If no primes are present
    // in the array
    if (primes.Count == 0)
    {
        for(int i = 0; i < N; i++)
        {
            Console.Write(-1 + " ");
        }
        return;
    }
 
    // Store the current prime
    int curr = 0;
    for(int i = 0; i < N; i++)
    {
         
        // If the no further
        // primes exist in the array
        if (curr == primes.Count - 1 ||
             
            // For all indices less than
            // that of the current prime
            i <= primes[curr])
        {
            Console.Write(
                arr[primes[curr]] + " ");
            continue;
        }
             
        // If the current prime is
        // nearer
        if (Math.Abs(primes[curr] - i) <
            Math.Abs(primes[curr + 1] - i))
        {
            Console.Write(
                arr[primes[curr]] + " ");
        }
             
        // If the next prime is nearer
        else
        {
             
            // Make the next prime
            // as the current
            curr++;
            Console.Write(
                arr[primes[curr]] + " ");
        }
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 6;
    int []arr = { 8, 7, 12, 15, 3, 11 };
     
    print_nearest_prime(arr, N);
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript program to find nearest
// prime number in the array
// for all array elements
let max = 10000000;
 
// Create a boolean array and set all
// entries it as false. A value in
// prime[i] will be true if i is not a
// prime, else false
let prime = new Array(max);
 
// Sieve of Eratosthenes function
function SieveOfEratosthenes(maxm)
{
    prime[0] = prime[1] = true;
       
    for(let i = 2; i * i <= maxm; i++)
    {
         
        // Update all multiples of i greater
        // than or equal to the square of it
        // numbers which are multiple of i
        // and are less than i^2 are already
        // been marked.
        if (!prime[i])
        {
            for(let j = i * i; j <= maxm; j += i)
            {
                prime[j] = true;
            }
        }
    }
}
 
// Function to find nearest
// prime number for all elements
function print_nearest_prime(arr, N)
{
    let maxm = Math.max(...arr);
       
    // Compute and store all prime
    // numbers up to maxm
    SieveOfEratosthenes(maxm);
   
    let primes = [];
       
    for(let i = 0; i < N; i++)
    {
         
        // Store the indices of
        // all primes
        if (!prime[arr[i]])
            primes.push(i);
    }
   
    // If no primes are present
    // in the array
    if (primes.length == 0)
    {
        for(let i = 0; i < N; i++)
        {
            document.write(-1 + " ");
        }
        return;
    }
   
    // Store the current prime
    let curr = 0;
    for(let i = 0; i < N; i++)
    {
         
        // If the no further
        // primes exist in the array
        if (curr == primes.length - 1 ||
         
            // For all indices less than
            // that of the current prime
            i <= primes[curr])
        {
            document.write(arr[primes[curr]] + " ");
            continue;
        }
         
        // If the current prime is
        // nearer
        if (Math.abs(primes[curr] - i) <
            Math.abs(primes[curr + 1] - i))
        {
            document.write(
            arr[primes[curr]] + " ");
        }
         
        // If the next prime is nearer
        else
        {
         
            // Make the next prime
            // as the current
            curr++;
            document.write(arr[primes[curr]] + " ");
        }
    }
}
 
// Driver code
let N = 6;
let arr = [ 8, 7, 12, 15, 3, 11 ];
 
print_nearest_prime(arr, N);
 
// This code is contributed by unknown2108
 
</script>
Producción: 

7 7 7 3 3 11

 

Complejidad de tiempo: O(maxm * (log(log(maxm))) + N)  
Espacio auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por KrishnaHare y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *