Sort only non-prime numbers of an array in increasing order

0 0 6 minutes read

Given an array of N integers. The task is to print the sorted array such that all numbers that are prime stay in the same place, sort only the non prime numbers.

Examples:

Input : arr[] = {10, 7, 6}
Output : 6 7 10

Input : arr[] = {100, 11, 500, 2, 17, 1}
Output : 1 11 100 2 17 500

Approach:

Traverse the array, take out all non-prime numbers and store them in a vector.
Now, sort the vector.
Then, traverse the array again and check if a number is prime, if yes then print it as it is. Otherwise, print a number from the vector.

To check whether a number is prime or not we can use sieve-of-eratosthenes.

Below is the implementation of above approach:

C++

// C++ program to sort only non primes
#include <bits/stdc++.h>
using namespace std;
 
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
bool prime[100005];
 
void SieveOfEratosthenes(int n)
{
 
    memset(prime, true, sizeof(prime));
 
    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
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to print the array such that
// only non primes are sorted
void sortedArray(int arr[], int n)
{
    SieveOfEratosthenes(100005);
 
    // vector v will store all non
    // prime numbers
    std::vector<int> v;
 
    // If not prime, insert into vector
    for (int i = 0; i < n; ++i) {
        if (prime[arr[i]] == 0)
            v.push_back(arr[i]);
    }
 
    // sorting vector of non primes
    sort(v.begin(), v.end());
 
    int j = 0;
    // print the required array
    for (int i = 0; i < n; ++i) {
        if (prime[arr[i]] == true)
            cout << arr[i] << " ";
        else {
            cout << v[j] << " ";
            j++;
        }
    }
}
 
// Driver Code
int main()
{
 
    int n = 6;
    int arr[] = { 100, 11, 500, 2, 17, 1 };
 
    sortedArray(arr, n);
 
    return 0;
}

Java

   
// Java program to sort only non primes
import java.util.*;
class solution
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
static boolean prime[] = new boolean[100006];
 
static void SieveOfEratosthenes(int n)
{
 
    for(int i=1;i<=n;i++)
    prime[i]=true;
    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
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to print the array such that
// only non primes are sorted
static void sortedArray(int arr[], int n)
{
    SieveOfEratosthenes(100005);
 
    // vector v will store all non
    // prime numbers
    Vector<Integer> v = new Vector<Integer>();
 
    // If not prime, insert into vector
    for (int i = 0; i < n; ++i) {
        if (prime[arr[i]]==false)
            v.add(arr[i]);
    }
 
    // sorting vector of non primes
    Collections.sort(v);
 
    int j = 0;
    // print the required array
    for (int i = 0; i < n; ++i) {
        if (prime[arr[i]] == true)
            System.out.print( arr[i] + " ");
        else {
            System.out.print( v.get(j) + " ");
            j++;
        }
    }
}
 
// Driver Code
public static void main(String args[])
{
 
    int n = 6;
    int arr[] = { 100, 11, 500, 2, 17, 1 };
 
    sortedArray(arr, n);
 
}
}
//contributed by Arnab Kundu

Python3

# Python3 program to sort only 
# non primes
 
# from math import sqrt method
from math import sqrt
 
# Create a boolean array "prime[0..n]" 
# and initialize all entries it as true.
# A value in prime[i] will  finally be false 
# if i is Not a prime, else true. 
prime = [0] * 100005
 
def SieveOfEratosthenes(n) :
 
    for i in range(len(prime)) :
        prime[i] = True
         
    prime[1] = False
 
    for p in range(2, int(sqrt(n)) + 1) :
         
        # If prime[p] is not changed, 
        # then it is a prime     
        if prime[p] == True :
 
            # Update all multiples of p 
            for i in range(p * 2, n, p) :
                prime[i] = False
 
 
# Function to print the array such that 
# only non primes are sorted 
def sortedArray(arr, n) :
     
    SieveOfEratosthenes(100005)
 
    # list v will store all non 
    # prime numbers 
    v = []
 
    # If not prime, insert into list
    for i in range(n) :
        if prime[arr[i]] == 0 :
            v.append(arr[i])
 
    # sorting list of non primes 
    v.sort()
 
    j = 0
 
    # print the required array
    for i in range(n) :
 
        if prime[arr[i]] == True :
            print(arr[i],end = " ")
        else :
            print(v[j],end = " ")
            j += 1
             
 
# Driver code
if __name__ == "__main__" :
 
    n = 6
    arr = [100, 11, 500, 2, 17, 1]
     
    sortedArray(arr, n)
     
# This code is contributed by 
# ANKITRAI1

C#

// C# program to sort only non primes
using System;
using System.Collections.Generic;
 
class GFG
{
    // Create a boolean array "prime[0..n]" 
    // and initialize all entries it as true.
    // A value in prime[i] will finally be
    // false if i is Not a prime, else true.
    static bool []prime = new bool[100006];
 
    static void SieveOfEratosthenes(int n)
    {
 
        for(int i = 1; i <= n; i++)
        prime[i] = true;
        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
                for (int i = p * 2; i <= n; i += p)
                    prime[i] = false;
            }
        }
    }
 
    // Function to print the array such that
    // only non primes are sorted
    static void sortedArray(int []arr, int n)
    {
        SieveOfEratosthenes(100005);
 
        // vector v will store all non
        // prime numbers
        List<int> v = new List<int>();
 
        // If not prime, insert into vector
        for (int i = 0; i < n; ++i)
        {
            if (prime[arr[i]] == false)
                v.Add(arr[i]);
        }
 
        // sorting vector of non primes
        v.Sort();
 
        int j = 0;
        // print the required array
        for (int i = 0; i < n; ++i) 
        {
            if (prime[arr[i]] == true)
                Console.Write( arr[i] + " ");
            else
            {
                Console.Write( v[j] + " ");
                j++;
            }
        }
    }
 
    // Driver Code
    public static void Main()
    {
 
        int n = 6;
        int []arr = { 100, 11, 500, 2, 17, 1 };
 
        sortedArray(arr, n);
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// JavaScript program to sort only non primes
 
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
prime = new Array(100005);
 
function SieveOfEratosthenes( n)
{
 
    prime.fill(true);
 
    prime[1] = false;
 
    for (var 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
            for (var i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to print the array such that
// only non primes are sorted
function sortedArray(arr, n)
{
    SieveOfEratosthenes(100005);
 
    // vector v will store all non
    // prime numbers
    var v = [];
 
    // If not prime, insert into vector
    for (var i = 0; i < n; ++i) {
        if (prime[arr[i]] == 0)
            v.push(arr[i]);
    }
 
    // sorting vector of non primes
    v.sort();
 
    var j = 0;
    // print the required array
    for (var i = 0; i < n; ++i) {
        if (prime[arr[i]] == true)
            document.write( arr[i] + " ");
        else {
            document.write( v[j] + " ");
            j++;
        }
    }
}
var n = 6;
var arr = [ 100, 11, 500, 2, 17, 1 ];
sortedArray(arr, n);
 
// This code is contributed by SoumikMondal
 
</script>

Output

1 11 100 2 17 500

Time Complexity: $O(Nlog(N))$

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!