View Discussion
Improve Article
Save Article
ReadDiscussView Discussion
Improve Article
Save Article
Given an array arr[] of N integers, the task is to remove all the prime numbers.
Examples:
Input: arr[] = {4, 6, 5, 3, 8, 7, 10, 11, 14, 15}
Output: 4 6 8 10 14 15
Input: arr[] = {2, 4, 7, 8, 9, 11}
Output: 4 8 9
Approach: Traverse the array and check if the current number is prime, if it is then left shift all the elements after it to remove this prime number and decrease the value of the array length. Repeat this for all
the elements of the array. To check the number is prime or not, use Sieve of Eratosthenes to generate all the primes.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
const int sz = 1e5;
bool isPrime[sz + 1];
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;
}
}
}
}
void printArray(int arr[], int len)
{
for (int i = 0; i < len; i++) {
cout << arr[i] << ' ';
}
}
void
removePrimes(int arr[], int len)
{
sieve();
for (int i = 0; i < len; i++) {
if (isPrime[arr[i]]) {
for (int j = i; j < len; j++) {
arr[j] = arr[j + 1];
}
i--;
len--;
}
}
printArray(arr, len);
}
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
class GFG
{
static int sz = (int) 1e5;
static boolean []isPrime = new boolean[sz + 1];
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;
}
}
}
}
static void printArray(int arr[], int len)
{
for
(int i = 0; i < len; i++)
{
System.out.print(arr[i] + " ");
}
}
static void removePrimes(int arr[], int len)
{
sieve();
for (int i = 0; i < len; i++)
{
if (isPrime[arr[i]])
{
for (int j = i; j < len-1; j++)
{
arr[j] = arr[j + 1];
}
i--;
len--;
}
}
printArray(arr, len);
}
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);
}
}
Python3
sz = 10**5
isPrime = [True for i in range(sz + 1)]
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
def printArray(arr, lenn):
for i in range(lenn):
print(arr[i], end = " ")
def removePrimes(arr, lenn):
sieve()
i = 0
while i < lenn:
if (isPrime[arr[i]]):
for j in range(i, lenn -
1):
arr[j] = arr[j + 1]
i -= 1
lenn -= 1
i += 1
printArray(arr, lenn)
if __name__ == '__main__':
arr =
[4, 6, 5, 3, 8, 7, 10, 11, 14, 15]
lenn = len(arr)
removePrimes(arr, lenn)
C#
using System;
class GFG
{
static
int sz = (int) 1e5;
static bool []isPrime = new bool[sz + 1];
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;
}
}
}
}
static void printArray(int []arr,
int len)
{
for (int i = 0; i < len; i++)
{
Console.Write(arr[i] + " ");
}
}
static void removePrimes(int []arr,
int len)
{
sieve();
for
(int i = 0; i < len; i++)
{
if (isPrime[arr[i]])
{
for (int j = i; j < len - 1; j++)
{
arr[j] = arr[j + 1];
}
i--;
len--;
}
}
printArray(arr, len);
}
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);
}
}
Javascript
<script>
const sz = 1e5;
let isPrime = new Array(sz + 1);
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 printArray(arr, len)
{
for(let i = 0; i < len; i++)
{
document.write(arr[i] + ' ');
}
}
function removePrimes(arr, len)
{
sieve();
for(let i = 0; i < len; i++)
{
if (isPrime[arr[i]])
{
for(let j = i; j < len; j++)
{
arr[j] = arr[j + 1];
}
i--;
len--;
}
}
printArray(arr, len);
}
let arr = [ 4, 6, 5, 3, 8, 7,
10, 11, 14, 15 ];
let len = arr.length;
removePrimes(arr, len);
</script>
