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