Dada una array arr[] de tamaño N de enteros positivos, la tarea es ordenar todos los números primos especiales en su posición relativa (sin afectar la posición de otros elementos). Un primo especial es un número primo que se puede representar como la suma de otros dos números primos.
Ejemplos:
Entrada: arr[] = {31, 5, 2, 1, 7}
Salida: 5 7 2 1 31
Los números primos especiales son 31 (29 + 2), 5 (2 + 3), 7 (5 + 2).
Ordenarlos, obtenemos 5, 7 y 31.
Entonces, la array original se convierte en {5, 7, 2, 1, 31}Entrada: arr[] = {3, 13, 11, 43, 2, 19, 17}
Salida: 3 13 11 19 2 43 17
Acercarse:
- Comience a recorrer la array y para cada elemento arr[i] , si arr[i] es un primo especial , guárdelo en un vector y actualice arr[i] = -1
- Después de que todos los números primos especiales se hayan almacenado en la lista, ordene la lista actualizada.
- Recorra nuevamente la array y para cada elemento,
- Si arr[i] = -1 , imprima el primer elemento de la lista que no se haya impreso antes.
- De lo contrario, imprime arr[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function for the Sieve of Eratosthenes
void sieveOfEratosthenes(bool prime[], int n)
{
prime[0] = prime[1] = false;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to sort the special primes
// in their relative positions
void sortSpecialPrimes(int arr[], int n)
{
// Maximum element from the array
int maxVal = *max_element(arr, arr + n);
// prime[i] will be true if i is a prime
bool prime[maxVal + 1];
memset(prime, true, sizeof(prime));
sieveOfEratosthenes(prime, maxVal);
// To store the special primes
// from the array
vector<int> list;
for (int i = 0; i < n; i++) {
// If current element is a special prime
if (prime[arr[i]] && prime[arr[i] - 2]) {
// Add it to the ArrayList
// and set arr[i] to -1
list.push_back(arr[i]);
arr[i] = -1;
}
}
// Sort the special primes
sort(list.begin(), list.end());
int j = 0;
for (int i = 0; i < n; i++) {
// Position of a special prime
if (arr[i] == -1)
cout << list[j++] << " ";
else
cout << arr[i] << " ";
}
}
// Driver code
int main()
{
int arr[] = { 31, 5, 2, 1, 7 };
int n = sizeof(arr) / sizeof(int);
sortSpecialPrimes(arr, n);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
// Function for the Sieve of Eratosthenes
static void sieveOfEratosthenes(boolean prime[],
int n)
{
prime[0] = prime[1] = false;
for(int p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
// greater than or equal to the
// square of it numbers which are
// multiple of p and are less than
// p^2 are already been marked.
for(int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to sort the special primes
// in their relative positions
static void sortSpecialPrimes(int arr[], int n)
{
// Maximum element from the array
int maxVal = Arrays.stream(arr).max().getAsInt();
// prime[i] will be true if i is a prime
boolean []prime = new boolean[maxVal + 1];
for(int i = 0; i < prime.length; i++)
prime[i] = true;
sieveOfEratosthenes(prime, maxVal);
// To store the special primes
// from the array
Vector<Integer> list = new Vector<Integer>();
for(int i = 0; i < n; i++)
{
// If current element is a special prime
if (prime[arr[i]] && prime[arr[i] - 2])
{
// Add it to the ArrayList
// and set arr[i] to -1
list.add(arr[i]);
arr[i] = -1;
}
}
// Sort the special primes
Collections.sort(list);
int j = 0;
for(int i = 0; i < n; i++)
{
// Position of a special prime
if (arr[i] == -1)
System.out.print(list.get(j++) + " ");
else
System.out.print(arr[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 31, 5, 2, 1, 7 };
int n = arr.length;
sortSpecialPrimes(arr, n);
}
}
// This code is contributed by PrinciRaj1992
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG{
// Function for the Sieve of Eratosthenes
static void sieveOfEratosthenes(bool []prime,
int n)
{
prime[0] = prime[1] = false;
for(int p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
// greater than or equal to the
// square of it numbers which are
// multiple of p and are less than
// p^2 are already been marked.
for(int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to sort the special primes
// in their relative positions
static void sortSpecialPrimes(int []arr, int n)
{
// Maximum element from the array
int maxVal = arr.Max();
// prime[i] will be true if i is a prime
bool []prime = new bool[maxVal + 1];
for(int i = 0; i < prime.Length; i++)
prime[i] = true;
sieveOfEratosthenes(prime, maxVal);
// To store the special primes
// from the array
List<int> list = new List<int>();
for(int i = 0; i < n; i++)
{
// If current element is a special prime
if (prime[arr[i]] && prime[arr[i] - 2])
{
// Add it to the List
// and set arr[i] to -1
list.Add(arr[i]);
arr[i] = -1;
}
}
// Sort the special primes
list.Sort();
int j = 0;
for(int i = 0; i < n; i++)
{
// Position of a special prime
if (arr[i] == -1)
Console.Write(list[j++] + " ");
else
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 31, 5, 2, 1, 7 };
int n = arr.Length;
sortSpecialPrimes(arr, n);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the above approach
// Function for the Sieve of Eratosthenes
function sieveOfEratosthenes(prime, n)
{
prime[0] = prime[1] = false;
for(let p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
// greater than or equal to the
// square of it numbers which are
// multiple of p and are less than
// p^2 are already been marked.
for(let i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to sort the special primes
// in their relative positions
function sortSpecialPrimes(arr, n)
{
// Maximum element from the array
let maxVal = Math.max(...arr);
// prime[i] will be true if i is a prime
let prime = Array.from(
{length: maxVal + 1}, (_, i) => 0);
for(let i = 0; i < prime.length; i++)
prime[i] = true;
sieveOfEratosthenes(prime, maxVal);
// To store the special primes
// from the array
let list = [];
for(let i = 0; i < n; i++)
{
// If current element is a special prime
if (prime[arr[i]] && prime[arr[i] - 2])
{
// Add it to the List
// and set arr[i] to -1
list.push(arr[i]);
arr[i] = -1;
}
}
// Sort the special primes
list.sort((a, b) => a - b);
let j = 0;
for(let i = 0; i < n; i++)
{
// Position of a special prime
if (arr[i] == -1)
document.write(list[j++] + " ");
else
document.write(arr[i] + " ");
}
}
// Driver Code
let arr = [ 31, 5, 2, 1, 7 ];
let n = arr.length;
sortSpecialPrimes(arr, n);
// This code is contributed by target_2
</script>
Producción:
5 7 2 1 31
Complejidad de tiempo: O(n * log n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por vvvchowdary143 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA