Dada una array arr[] de N enteros, la tarea es eliminar todos los números primos.
Ejemplos:
Entrada: arr[] = {4, 6, 5, 3, 8, 7, 10, 11, 14, 15}
Salida: 4 6 8 10 14 15Entrada: arr[] = {2, 4, 7, 8, 9, 11}
Salida: 4 8 9
Enfoque: recorra la array y verifique si el número actual es primo, si lo es, desplace a la izquierda todos los elementos después de él para eliminar este número primo y disminuir el valor de la longitud de la array. Repita esto para todos los elementos de la array. Para comprobar si el número es primo o no, utilice la criba de Eratóstenes para generar todos los números primos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int sz = 1e5;
bool isPrime[sz + 1];
// Function for Sieve of Eratosthenes
void sieve()
{
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= sz; i++) {
if (isPrime[i]) {
for (int j = i * i; j < sz; j += i) {
isPrime[j] = false;
}
}
}
}
// Function to print the elements of the array
void printArray(int arr[], int len)
{
for (int i = 0; i < len; i++) {
cout << arr[i] << ' ';
}
}
// Function to remove all the prime numbers
void removePrimes(int arr[], int len)
{
// Generate primes
sieve();
// Traverse the array
for (int i = 0; i < len; i++) {
// If the current element is prime
if (isPrime[arr[i]]) {
// Shift all the elements on the
// right of it to the left
for (int j = i; j < len; j++) {
arr[j] = arr[j + 1];
}
// Decrease the loop counter by 1
// to check the shifted element
i--;
// Decrease the length
len--;
}
}
// Print the updated array
printArray(arr, len);
}
// Driver code
int main()
{
int arr[] = { 4, 6, 5, 3, 8, 7,
10, 11, 14, 15 };
int len = sizeof(arr) / sizeof(int);
removePrimes(arr, len);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int sz = (int) 1e5;
static boolean []isPrime = new boolean[sz + 1];
// Function for Sieve of Eratosthenes
static void sieve()
{
for (int i = 0; i < sz + 1; i++)
isPrime[i] = true;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= sz; i++)
{
if (isPrime[i])
{
for (int j = i * i; j < sz; j += i)
{
isPrime[j] = false;
}
}
}
}
// Function to print the elements of the array
static void printArray(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
System.out.print(arr[i] + " ");
}
}
// Function to remove all the prime numbers
static void removePrimes(int arr[], int len)
{
// Generate primes
sieve();
// Traverse the array
for (int i = 0; i < len; i++)
{
// If the current element is prime
if (isPrime[arr[i]])
{
// Shift all the elements on the
// right of it to the left
for (int j = i; j < len-1; j++)
{
arr[j] = arr[j + 1];
}
// Decrease the loop counter by 1
// to check the shifted element
i--;
// Decrease the length
len--;
}
}
// Print the updated array
printArray(arr, len);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 6, 5, 3, 8, 7,
10, 11, 14, 15 };
int len = arr.length;
removePrimes(arr, len);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach sz = 10**5 isPrime = [True for i in range(sz + 1)] # Function for Sieve of Eratosthenes def sieve(): isPrime[0] = isPrime[1] = False i = 2 while i * i < sz: if (isPrime[i]): for j in range(i * i, sz, i): isPrime[j] = False i += 1 # Function to print the elements of the array def printArray(arr, lenn): for i in range(lenn): print(arr[i], end = " ") # Function to remove all the prime numbers def removePrimes(arr, lenn): # Generate primes sieve() # Traverse the array i = 0 while i < lenn: # If the current element is prime if (isPrime[arr[i]]): # Shift all the elements on the # right of it to the left for j in range(i, lenn - 1): arr[j] = arr[j + 1] # Decrease the loop counter by 1 # to check the shifted element i -= 1 # Decrease the length lenn -= 1 i += 1 # Print the updated array printArray(arr, lenn) # Driver code if __name__ == '__main__': arr = [4, 6, 5, 3, 8, 7, 10, 11, 14, 15] lenn = len(arr) removePrimes(arr, lenn) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
static int sz = (int) 1e5;
static bool []isPrime = new bool[sz + 1];
// Function for Sieve of Eratosthenes
static void sieve()
{
for (int i = 0; i < sz + 1; i++)
isPrime[i] = true;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= sz; i++)
{
if (isPrime[i])
{
for (int j = i * i;
j < sz; j += i)
{
isPrime[j] = false;
}
}
}
}
// Function to print the elements
// of the array
static void printArray(int []arr,
int len)
{
for (int i = 0; i < len; i++)
{
Console.Write(arr[i] + " ");
}
}
// Function to remove
// all the prime numbers
static void removePrimes(int []arr,
int len)
{
// Generate primes
sieve();
// Traverse the array
for (int i = 0; i < len; i++)
{
// If the current element is prime
if (isPrime[arr[i]])
{
// Shift all the elements on the
// right of it to the left
for (int j = i; j < len - 1; j++)
{
arr[j] = arr[j + 1];
}
// Decrease the loop counter by 1
// to check the shifted element
i--;
// Decrease the length
len--;
}
}
// Print the updated array
printArray(arr, len);
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 4, 6, 5, 3, 8, 7,
10, 11, 14, 15 };
int len = arr.Length;
removePrimes(arr, len);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
const sz = 1e5;
let isPrime = new Array(sz + 1);
// Function for Sieve of Eratosthenes
function sieve()
{
isPrime.fill(true)
isPrime[0] = isPrime[1] = false;
for(let i = 2; i * i <= sz; i++)
{
if (isPrime[i])
{
for(let j = i * i; j < sz; j += i)
{
isPrime[j] = false;
}
}
}
}
// Function to print the elements of the array
function printArray(arr, len)
{
for(let i = 0; i < len; i++)
{
document.write(arr[i] + ' ');
}
}
// Function to remove all the prime numbers
function removePrimes(arr, len)
{
// Generate primes
sieve();
// Traverse the array
for(let i = 0; i < len; i++)
{
// If the current element is prime
if (isPrime[arr[i]])
{
// Shift all the elements on the
// right of it to the left
for(let j = i; j < len; j++)
{
arr[j] = arr[j + 1];
}
// Decrease the loop counter by 1
// to check the shifted element
i--;
// Decrease the length
len--;
}
}
// Print the updated array
printArray(arr, len);
}
// Driver code
let arr = [ 4, 6, 5, 3, 8, 7,
10, 11, 14, 15 ];
let len = arr.length;
removePrimes(arr, len);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
4 6 8 10 14 15