You are given a list of n numbers each of which is either prime or composite

Sort prime numbers of an array in descending order

Given an array of integers ‘arr’, the task is to sort all the prime numbers from the array in descending order in their relative positions i.e. other positions of the other elements must not be affected.
Examples:

Table of Contents Show

Sort prime numbers of an array in descending order
Answer to Question #179421 in Python for CHANDRASENA REDDY CHADA
Leave a comment
Ask Your question
Prime & Composite Numbers
Python Program to Check Prime Number

Input: arr[] = {2, 5, 8, 4, 3} Output: 5 3 8 4 2 Input: arr[] = {10, 12, 2, 6, 5} Output: 10 12 5 6 2

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach:

Create a sieve to check whether an element is prime or not in O(1).
Traverse the array and check if the number is prime. If it is prime, store it in a vector.
Then, sort the vector in descending order.
Again traverse the array and replace the prime numbers with the vector elements one by one.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>

using namespace std;

bool prime[100005];

void SieveOfEratosthenes(int n)
{

memset(prime, true, sizeof(prime));

// false here indicates

// that it is not 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]) {

// Update all multiples of p,

// set them to non-prime

for (int i = p * 2; i <= n; i += p)

prime[i] = false;

}

}
}
// Function that sorts
// all the prime numbers
// from the array in descending

void sortPrimes(int arr[], int n)
{

SieveOfEratosthenes(100005);

// this vector will contain

// prime numbers to sort

vector<int> v;

for (int i = 0; i < n; i++) {

// if the element is prime

if (prime[arr[i]])

v.push_back(arr[i]);

}

sort(v.begin(), v.end(), greater<int>());

int j = 0;

// update the array elements

for (int i = 0; i < n; i++) {

if (prime[arr[i]])

arr[i] = v[j++];

}
}
// Driver code

int main()
{

int arr[] = { 4, 3, 2, 6, 100, 17 };

int n = sizeof(arr) / sizeof(arr[0]);

sortPrimes(arr, n);

// print the results.

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";

}

return 0;
}

Java

// Java implementation of the approach

import java.util.*;

class GFG
{

static boolean prime[] = new boolean[100005];

static void SieveOfEratosthenes(int n)

{

Arrays.fill(prime, true);

// false here indicates

// that it is not 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]) {

// Update all multiples of p,

// set them to non-prime

for (int i = p * 2; i < n; i += p)

{

prime[i] = false;

}

}

}

}

// Function that sorts

// all the prime numbers

// from the array in descending

static void sortPrimes(int arr[], int n)

{

SieveOfEratosthenes(100005);

// this vector will contain

// prime numbers to sort

Vector<Integer> v = new Vector<Integer>();

for (int i = 0; i < n; i++)

{

// if the element is prime

if (prime[arr[i]])

{

v.add(arr[i]);

}

}

Comparator comparator = Collections.reverseOrder();

Collections.sort(v, comparator);

int j = 0;

// update the array elements

for (int i = 0; i < n; i++)

{

if (prime[arr[i]])

{

arr[i] = v.get(j++);

}

}

}

// Driver code

public static void main(String[] args)

{

int arr[] = {4, 3, 2, 6, 100, 17};

int n = arr.length;

sortPrimes(arr, n);

// print the results.

for (int i = 0; i < n; i++)

{

System.out.print(arr[i] + " ");

}

}
}
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach 

def SieveOfEratosthenes(n):

# false here indicates

# that it is not prime

prime[1] = False

p = 2

while p * p <= n:

# If prime[p] is not changed,

# then it is a prime

if prime[p]:

# Update all multiples of p,

# set them to non-prime

for i in range(p * 2, n + 1, p):

prime[i] = False

p += 1
# Function that sorts all the prime 
# numbers from the array in descending 

def sortPrimes(arr, n):

SieveOfEratosthenes(100005)

# This vector will contain

# prime numbers to sort

v = []

for i in range(0, n):

# If the element is prime

if prime[arr[i]]:

v.append(arr[i])

v.sort(reverse = True)

j = 0

# update the array elements

for i in range(0, n):

if prime[arr[i]]:

arr[i] = v[j]

j += 1

return arr

# Driver code 

if __name__ == "__main__":

arr = [4, 3, 2, 6, 100, 17]

n = len(arr)

prime = [True] * 100006

arr = sortPrimes(arr, n)

# print the results.

for i in range(0, n):

print(arr[i], end = " ")

# This code is contributed by Rituraj Jain

// C# implementation of the approach

using System;

using System.Collections.Generic;

class GFG
{

static bool []prime = new bool[100005];

static void SieveOfEratosthenes(int n)

{

for(int i = 0; i < 100005; i++)

prime[i] = true;

// false here indicates

// that it is not 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])

{

// Update all multiples of p,

// set them to non-prime

for (int i = p * 2; i < n; i += p)

{

prime[i] = false;

}

}

}

}

// Function that sorts

// all the prime numbers

// from the array in descending

static void sortPrimes(int []arr, int n)

{

SieveOfEratosthenes(100005);

// this vector will contain

// prime numbers to sort

List<int> v = new List<int>();

for (int i = 0; i < n; i++)

{

// if the element is prime

if (prime[arr[i]])

{

v.Add(arr[i]);

}

}

v.Sort();

v.Reverse();

int j = 0;

// update the array elements

for (int i = 0; i < n; i++)

{

if (prime[arr[i]])

{

arr[i] = v[j++];

}

}

}

// Driver code

public static void Main(String[] args)

{

int []arr = {4, 3, 2, 6, 100, 17};

int n = arr.Length;

sortPrimes(arr, n);

// print the results.

for (int i = 0; i < n; i++)

{

Console.Write(arr[i] + " ");

}

}
}
// This code contributed by Rajput-Ji

Javascript

<script>
// Javascript implementation of the approach

var prime = Array(100005).fill(true);

function SieveOfEratosthenes( n)
{

// false here indicates

// that it is not prime

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]) {

// Update all multiples of p,

// set them to non-prime

for (var i = p * 2; i <= n; i += p)

prime[i] = false;

}

}
}
// Function that sorts
// all the prime numbers
// from the array in descending

function sortPrimes(arr, n)
{

SieveOfEratosthenes(100005);

// this vector will contain

// prime numbers to sort

var v = [];

for (var i = 0; i < n; i++) {

// if the element is prime

if (prime[arr[i]])

v.push(arr[i]);

}

v.sort((a,b)=>b-a)

var j = 0;

// update the array elements

for (var i = 0; i < n; i++) {

if (prime[arr[i]])

arr[i] = v[j++];

}
}
// Driver code

var arr = [4, 3, 2, 6, 100, 17 ];

var n = arr.length;
sortPrimes(arr, n);
// print the results.

for (var i = 0; i < n; i++) {

document.write( arr[i] + " ");
}
</script>

Output: 4 17 3 6 100 2

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.

Article Tags :

Arrays

Competitive Programming

Mathematical

Sorting

Prime Number

sieve

Practice Tags :

Arrays

Mathematical

Sorting

Prime Number

sieve

Read Full Article

Answer to Question #179421 in Python for CHANDRASENA REDDY CHADA

2021-04-08T00:33:14-04:00

Answers>

Programming & Computer Science>

Python

Question #179421

Sum of Prime Numbers In the Input

Given a list of integers, write a program to print the sum of all prime numbers in the list of integers.

Note: One is neither prime nor composite number.Input

The input will be a single line containing space-separated integers..Output

The output should be a single line containing the sum of all prime numbers from 1 to N.Explanation

For example, if the given list of integers are

2 4 5 6 7 3 8

As 2, 3, 5 and 7 are prime numbers, your code should print the sum of these numbers. So the output should be 17.

Sample Input 1

2 4 5 6 7 3 8

Sample Output 1

Sample Input 2

65 87 96 31 32 86 57 69 20 42

Sample Output 2

Expert's answer

2021-04-08T02:59:07-0400

# Program to computer sum # of prime number in a given range # from math lib import sqrt method from math import sqrt # Function to compute the prime number # Time Complexity is O(sqrt(N)) def checkPrime(numberToCheck) : if numberToCheck == 1 : return False for i in range(2, int(sqrt(numberToCheck)) + 1) : if numberToCheck % i == 0 : return False return True # Function to iterate the loop # from l to r. If the current # number is prime, sum the value def primeSum(l, r) : sum = 0 for i in range(r, (l - 1), -1) : # Check for prime isPrime = checkPrime(i) if (isPrime) : # Sum the prime number sum += i return sum # Time Complexity is O(r x sqrt(N)) # Driver code if __name__ == "__main__" : l, r = 4, 13 # Call the function with l and r print(primeSum(l, r))

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Place free inquiry

Calculate the price

Learn more about our help with Assignments: Python

Comments

No comments. Be the first!

Thank you! Your comments have been successfully added. However, they need to be checked by the moderator before being published.

Post

Ask Your question

Ask

Prime & Composite Numbers

Definition: A prime number is a whole number with exactly two integral divisors, 1 and itself.

The number 1 is not a prime, since it has only one divisor.

So the smallest prime numbers are:

2,3,5,7,⋯

The number 4 is not prime, since it has three divisors ( 1 , 2 , and 4 ), and 6 is not prime, since it has four divisors ( 1 , 2 , 3 , and 6 ).

Definition: A composite number is a whole number with more than two integral divisors.

So all whole numbers (except 0 and 1 ) are either prime or composite.

Example:

43 is prime, since its only divisors are 1 and 43 .

44 is composite, since it has 1,2,4,11,22 and 44 as divisors.

Python Program to Check Prime Number

Example to check whether an integer is a prime number or not using for loop and if...else statement. If the number is not prime, it's explained in output why it is not a prime number.

To understand this example, you should have the knowledge of the following Python programming topics:

Python if...else Statement
Python for Loop
Python break and continue

A positive integer greater than 1 which has no other factors except 1 and the number itself is called a prime number. 2, 3, 5, 7 etc. are prime numbers as they do not have any other factors. But 6 is not prime (it is composite) since, 2 x 3 = 6.