Dada una array arr[] de tamaño N , la tarea es reorganizar los elementos de la array de modo que todos los números primos se coloquen antes de los números no primos.
Ejemplos:
Entrada: arr[] = {1, 8, 2, 3, 4, 5, 7, 20}
Salida: 7 5 2 3 4 8 1 20
Explicación:
La salida consta de todos los números primos 7 5 2 3, seguidos de Números no primos 4 8 1 20.Entrada: arr[] = {2, 3, 4, 5, 6, 7, 8, 9, 10}
Salida: 2 3 7 5 6 4 8 9 10
Enfoque ingenuo: el enfoque más simple para resolver este problema es hacer dos arrays para almacenar los elementos primos y no primos de la array respectivamente e imprimir los números primos seguidos de los números no primos.
Complejidad de tiempo: O(N*sqrt(N))
Espacio auxiliar: O(N)
Enfoque alternativo: para optimizar el espacio auxiliar del enfoque anterior, la idea de resolver este problema es utilizar el enfoque de dos puntos . Siga los pasos a continuación para resolver el problema:
- Inicialice dos punteros a la izquierda como 0 y a la derecha hasta el final de la array como (N – 1) .
- Atraviese la array hasta que la izquierda sea menor que la derecha y haga lo siguiente:
- Siga incrementando el puntero izquierdo hasta que el elemento que apunta al índice izquierdo sea un número primo.
- Siga disminuyendo el puntero derecho hasta que el elemento que apunta al índice izquierdo no sea un número primo.
- Si la izquierda es menor que la derecha , intercambie arr[izquierda] y arr[derecha] e incremente la izquierda y disminuya la derecha en 1 .
- Después de los pasos anteriores, imprima la array de actualización arr[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to swap two numbers a and b
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Function to check if a number n
// is a prime number of not
bool isPrime(int n)
{
// Edges Cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// To skip middle five numbers
if (n % 2 == 0 || n % 3 == 0)
return false;
// Checks for prime or non prime
for (int i = 5;
i * i <= n; i = i + 6) {
// If n is divisible by i
// or i + 2, return false
if (n % i == 0
|| n % (i + 2) == 0)
return false;
}
// Otherwise, the
// number is prime
return true;
}
// Function to segregate the primes
// and non-primes present in an array
void segregatePrimeNonPrime(
int arr[], int N)
{
// Initialize left and right pointers
int left = 0, right = N - 1;
// Traverse the array
while (left < right) {
// Increment left while array
// element at left is prime
while (isPrime(arr[left]))
left++;
// Decrement right while array
// element at right is non-prime
while (!isPrime(arr[right]))
right--;
// If left < right, then swap
// arr[left] and arr[right]
if (left < right) {
// Swapp arr[left] and arr[right]
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
// Print segregated array
for (int i = 0; i < N; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 6, 7, 8, 9, 10 };
int N = sizeof(arr) / sizeof(arr[0]);
segregatePrimeNonPrime(arr, N);
return 0;
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Function to check if a number n
// is a prime number of not
static boolean isPrime(int n)
{
// Edges Cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// To skip middle five numbers
if (n % 2 == 0 || n % 3 == 0)
return false;
// Checks for prime or non prime
for (int i = 5; i * i <= n; i = i + 6) {
// If n is divisible by i
// or i + 2, return false
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
// Otherwise, the
// number is prime
return true;
}
// Function to segregate the primes
// and non-primes present in an array
static void segregatePrimeNonPrime(int arr[], int N)
{
// Initialize left and right pointers
int left = 0, right = N - 1;
// Traverse the array
while (left < right) {
// Increment left while array
// element at left is prime
while (isPrime(arr[left]))
left++;
// Decrement right while array
// element at right is non-prime
while (!isPrime(arr[right]))
right--;
// If left < right, then swap
// arr[left] and arr[right]
if (left < right) {
// Swapp arr[left] and arr[right]
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
left++;
right--;
}
}
// Print segregated array
for (int i = 0; i < N; i++)
System.out.print(arr[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 6, 7, 8, 9, 10 };
int N = arr.length;
segregatePrimeNonPrime(arr, N);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to check if a number n # is a prime number of not def isPrime(n): # Edges Cases if (n <= 1): return False if (n <= 3): return True # To skip middle five numbers if (n % 2 == 0 or n % 3 == 0): return False # Checks for prime or non prime i = 5 while (i * i <= n): # If n is divisible by i or i + 2, # return False if (n % i == 0 or n % (i + 2) == 0): return False i += 6 # Otherwise, the number is prime return True # Function to segregate the primes and # non-primes present in an array def segregatePrimeNonPrime(arr, N): # Initialize left and right pointers left, right = 0, N - 1 # Traverse the array while (left < right): # Increment left while array element # at left is prime while (isPrime(arr[left])): left += 1 # Decrement right while array element # at right is non-prime while (not isPrime(arr[right])): right -= 1 # If left < right, then swap # arr[left] and arr[right] if (left < right): # Swapp arr[left] and arr[right] arr[left], arr[right] = arr[right], arr[left] left += 1 right -= 1 # Print segregated array for num in arr: print(num, end = " ") # Driver code arr = [ 2, 3, 4, 6, 7, 8, 9, 10 ] N = len(arr) segregatePrimeNonPrime(arr, N) # This code is contributed by girishthatte
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if a number n
// is a prime number of not
static bool isPrime(int n)
{
// Edges Cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// To skip middle five numbers
if (n % 2 == 0 || n % 3 == 0)
return false;
// Checks for prime or non prime
for(int i = 5; i * i <= n; i = i + 6)
{
// If n is divisible by i
// or i + 2, return false
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
// Otherwise, the
// number is prime
return true;
}
// Function to segregate the primes
// and non-primes present in an array
static void segregatePrimeNonPrime(int[] arr, int N)
{
// Initialize left and right pointers
int left = 0, right = N - 1;
// Traverse the array
while (left < right)
{
// Increment left while array
// element at left is prime
while (isPrime(arr[left]))
left++;
// Decrement right while array
// element at right is non-prime
while (!isPrime(arr[right]))
right--;
// If left < right, then swap
// arr[left] and arr[right]
if (left < right)
{
// Swapp arr[left] and arr[right]
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
left++;
right--;
}
}
// Print segregated array
for(int i = 0; i < N; i++)
Console.Write(arr[i] + " ");
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 2, 3, 4, 6, 7, 8, 9, 10 };
int N = arr.Length;
segregatePrimeNonPrime(arr, N);
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program implementation
// of the approach
// Function to generate prime numbers
// using Sieve of Eratosthenes
function SieveOfEratosthenes(prime, n)
{
for(let p = 2; p * p <= n; p++)
{
// If prime[p] is unchanged,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for(let i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to segregate the primes and non-primes
function segregatePrimeNonPrime(prime, arr, N)
{
// Generate all primes till 10^
SieveOfEratosthenes(prime, 10000000);
// Initialize left and right
let left = 0, right = N - 1;
// Traverse the array
while (left < right)
{
// Increment left while array element
// at left is prime
while (prime[arr[left]])
left++;
// Decrement right while array element
// at right is non-prime
while (!prime[arr[right]])
right--;
// If left < right, then swap arr[left]
// and arr[right]
if (left < right)
{
// Swap arr[left] and arr[right]
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
// Print segregated array
for(let i = 0; i < N; i++)
document.write(arr[i] + " ");
}
// Driver Code
let prime = Array.from({length: 10000001}, (_, i) => true);
let arr = [ 2, 3, 4, 6, 7, 8, 9, 10 ];
let N = arr.length;
// Function Call
segregatePrimeNonPrime(prime, arr, N);
</script>
Producción:
2 3 7 6 4 8 9 10
Complejidad de tiempo: O(N*sqrt(N))
Espacio auxiliar: O(1), ya que no se ha tomado espacio extra.
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la criba de Eratóstenes para encontrar si el número es primo o no primo en tiempo constante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
bool prime[10000001];
// Function to swap two numbers a and b
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Function to generate prime numbers
// using Sieve of Eratosthenes
void SieveOfEratosthenes(int n)
{
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= n; p++) {
// If prime[p] is unchanged,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * p;
i <= n; i += p)
prime[i] = false;
}
}
}
// Function to segregate the primes
// and non-primes
void segregatePrimeNonPrime(
int arr[], int N)
{
// Generate all primes till 10^7
SieveOfEratosthenes(10000000);
// Initialize left and right
int left = 0, right = N - 1;
// Traverse the array
while (left < right) {
// Increment left while array
// element at left is prime
while (prime[arr[left]])
left++;
// Decrement right while array
// element at right is non-prime
while (!prime[arr[right]])
right--;
// If left < right, then swap
// arr[left] and arr[right]
if (left < right) {
// Swap arr[left] and arr[right]
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
// Print segregated array
for (int i = 0; i < N; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 6, 7, 8, 9, 10 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
segregatePrimeNonPrime(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to generate prime numbers
// using Sieve of Eratosthenes
public static void SieveOfEratosthenes(boolean[] prime,
int n)
{
for(int p = 2; p * p <= n; p++)
{
// If prime[p] is unchanged,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for(int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to segregate the primes and non-primes
public static void segregatePrimeNonPrime(boolean[] prime,
int arr[], int N)
{
// Generate all primes till 10^
SieveOfEratosthenes(prime, 10000000);
// Initialize left and right
int left = 0, right = N - 1;
// Traverse the array
while (left < right)
{
// Increment left while array element
// at left is prime
while (prime[arr[left]])
left++;
// Decrement right while array element
// at right is non-prime
while (!prime[arr[right]])
right--;
// If left < right, then swap arr[left]
// and arr[right]
if (left < right)
{
// Swap arr[left] and arr[right]
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
// Print segregated array
for(int i = 0; i < N; i++)
System.out.printf(arr[i] + " ");
}
// Driver code
public static void main(String[] args)
{
boolean[] prime = new boolean[10000001];
Arrays.fill(prime, true);
int arr[] = { 2, 3, 4, 6, 7, 8, 9, 10 };
int N = arr.length;
// Function Call
segregatePrimeNonPrime(prime, arr, N);
}
}
// This code is contributed by girishthatte
Python3
# Python3 program for the above approach # Function to generate prime numbers # using Sieve of Eratosthenes def SieveOfEratosthenes(prime, n): p = 2 while (p * p <= n): # If prime[p] is unchanged, # then it is a prime if (prime[p] == True): # Update all multiples of p i = p * p while (i <= n): prime[i] = False i += p p += 1 # Function to segregate the primes and non-primes def segregatePrimeNonPrime(prime, arr, N): # Generate all primes till 10^7 SieveOfEratosthenes(prime, 10000000) # Initialize left and right left, right = 0, N - 1 # Traverse the array while (left < right): # Increment left while array element # at left is prime while (prime[arr[left]]): left += 1 # Decrement right while array element # at right is non-prime while (not prime[arr[right]]): right -= 1 # If left < right, then swap arr[left] # and arr[right] if (left < right): # Swap arr[left] and arr[right] arr[left], arr[right] = arr[right], arr[left] left += 1 right -= 1 # Print segregated array for num in arr: print(num, end = " ") # Driver code arr = [ 2, 3, 4, 6, 7, 8, 9, 10 ] N = len(arr) prime = [True] * 10000001 # Function Call segregatePrimeNonPrime(prime, arr, N) # This code is contributed by girishthatte
C#
// C# program for the above approach
using System;
class GFG{
// Function to generate prime numbers
// using Sieve of Eratosthenes
public static void SieveOfEratosthenes(bool[] prime,
int n)
{
for(int p = 2; p * p <= n; p++)
{
// If prime[p] is unchanged,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for(int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to segregate the primes and non-primes
public static void segregatePrimeNonPrime(bool[] prime,
int []arr, int N)
{
// Generate all primes till 10^
SieveOfEratosthenes(prime, 10000000);
// Initialize left and right
int left = 0, right = N - 1;
// Traverse the array
while (left < right)
{
// Increment left while array element
// at left is prime
while (prime[arr[left]])
left++;
// Decrement right while array element
// at right is non-prime
while (!prime[arr[right]])
right--;
// If left < right, then swap arr[left]
// and arr[right]
if (left < right)
{
// Swap arr[left] and arr[right]
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
// Print segregated array
for(int i = 0; i < N; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
bool[] prime = new bool[10000001];
for(int i = 0; i < prime.Length; i++)
prime[i] = true;
int []arr = { 2, 3, 4, 6, 7, 8, 9, 10 };
int N = arr.Length;
// Function Call
segregatePrimeNonPrime(prime, arr, N);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function to generate prime numbers
// using Sieve of Eratosthenes
function SieveOfEratosthenes(prime, n)
{
for(let p = 2; p * p <= n; p++)
{
// If prime[p] is unchanged,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for(let i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to segregate the primes and non-primes
function segregatePrimeNonPrime(prime, arr, N)
{
// Generate all primes till 10^
SieveOfEratosthenes(prime, 10000000);
// Initialize left and right
let left = 0, right = N - 1;
// Traverse the array
while (left < right)
{
// Increment left while array element
// at left is prime
while (prime[arr[left]])
left++;
// Decrement right while array element
// at right is non-prime
while (!prime[arr[right]])
right--;
// If left < right, then swap arr[left]
// and arr[right]
if (left < right)
{
// Swap arr[left] and arr[right]
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
// Print segregated array
for(let i = 0; i < N; i++)
document.write(arr[i] + " ");
}
// Driver Code
let prime = Array.from({length: 10000001},
(_, i) => true);
let arr = [ 2, 3, 4, 6, 7, 8, 9, 10 ];
let N = arr.length;
// Function Call
segregatePrimeNonPrime(prime, arr, N);
</script>
Producción:
2 3 7 6 4 8 9 10
Complejidad de tiempo: O(N*log(log(N)))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por partapupraneeth y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA