Sort all special primes in their relative positions
Given an array arr[] of size N of positive integers, the task is to sort all the special primes in their relative position (without affecting the position of other elements). A special prime is a prime number which can be represented as the sum of two other prime numbers.
Examples:
Input: arr[] = {31, 5, 2, 1, 7}
Output: 5 7 2 1 31
The special primes are 31 (29 + 2), 5 (2 + 3), 7 (5 + 2).
Sort them, we get 5, 7 and 31.
So, the original array becomes {5, 7, 2, 1, 31}Input: arr[] = {3, 13, 11, 43, 2, 19, 17}
Output: 3 13 11 19 2 43 17
Approach:
- Start traversing the array and for every element arr[i], if arr[i] is a special prime then store it in a vector and update arr[i] = -1
- After all the special primes have been stored in the list, sort the updated list.
- Again traverse the array and for every element,
- If arr[i] = -1 then print the first element from the list that hasn’t been printed before.
- Else, print arr[i].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function for the Sieve of Eratosthenes void sieveOfEratosthenes( bool prime[], int n) { prime[0] = 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 greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i <= n; i += p) prime[i] = false ; } } } // Function to sort the special primes // in their relative positions void sortSpecialPrimes( int arr[], int n) { // Maximum element from the array int maxVal = *max_element(arr, arr + n); // prime[i] will be true if i is a prime bool prime[maxVal + 1]; memset (prime, true , sizeof (prime)); sieveOfEratosthenes(prime, maxVal); // To store the special primes // from the array vector< int > list; for ( int i = 0; i < n; i++) { // If current element is a special prime if (prime[arr[i]] && prime[arr[i] - 2]) { // Add it to the ArrayList // and set arr[i] to -1 list.push_back(arr[i]); arr[i] = -1; } } // Sort the special primes sort(list.begin(), list.end()); int j = 0; for ( int i = 0; i < n; i++) { // Position of a special prime if (arr[i] == -1) cout << list[j++] << " " ; else cout << arr[i] << " " ; } } // Driver code int main() { int arr[] = { 31, 5, 2, 1, 7 }; int n = sizeof (arr) / sizeof ( int ); sortSpecialPrimes(arr, n); return 0; } |
Java
// Java implementation of the above approach import java.util.*; class GFG{ // Function for the Sieve of Eratosthenes static void sieveOfEratosthenes( boolean prime[], int n) { prime[ 0 ] = 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 // greater than or equal to the // square of it numbers which are // multiple of p and are less than // p^2 are already been marked. for ( int i = p * p; i <= n; i += p) prime[i] = false ; } } } // Function to sort the special primes // in their relative positions static void sortSpecialPrimes( int arr[], int n) { // Maximum element from the array int maxVal = Arrays.stream(arr).max().getAsInt(); // prime[i] will be true if i is a prime boolean []prime = new boolean [maxVal + 1 ]; for ( int i = 0 ; i < prime.length; i++) prime[i] = true ; sieveOfEratosthenes(prime, maxVal); // To store the special primes // from the array Vector<Integer> list = new Vector<Integer>(); for ( int i = 0 ; i < n; i++) { // If current element is a special prime if (prime[arr[i]] && prime[arr[i] - 2 ]) { // Add it to the ArrayList // and set arr[i] to -1 list.add(arr[i]); arr[i] = - 1 ; } } // Sort the special primes Collections.sort(list); int j = 0 ; for ( int i = 0 ; i < n; i++) { // Position of a special prime if (arr[i] == - 1 ) System.out.print(list.get(j++) + " " ); else System.out.print(arr[i] + " " ); } } // Driver code public static void main(String[] args) { int arr[] = { 31 , 5 , 2 , 1 , 7 }; int n = arr.length; sortSpecialPrimes(arr, n); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the above approach # Function for the Sieve of Eratosthenes def sieveOfEratosthenes(prime, n): prime[ 0 ] = False prime[ 1 ] = False ; for p in range ( 2 , 1 + int (n * * 0.5 )): # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all multiples of p # greater than or equal to the # square of it numbers which are # multiple of p and are less than # p^2 are already been marked. for i in range (p * p, 1 + n, p): prime[i] = False ; # Function to sort the special primes # in their relative positions def sortSpecialPrimes(arr, n): # Maximum element from the array maxVal = max (arr) # prime[i] will be true if i is a prime prime = [ False for _ in range (maxVal + 1 )] for i in range ( len (prime)): prime[i] = True ; sieveOfEratosthenes(prime, maxVal); # To store the special primes # from the array list1 = []; for i in range (n): # If current element is a special prime if (prime[arr[i]] and prime[arr[i] - 2 ]) : # Add it to the List # and set arr[i] to -1 list1.append(arr[i]); arr[i] = - 1 ; # Sort the special primes list1.sort() j = 0 ; for i in range (n): # Position of a special prime if (arr[i] = = - 1 ): print (list1[j], end = " " ) j + = 1 else : print (arr[i], end = " " ) # Driver Code arr = [ 31 , 5 , 2 , 1 , 7 ]; n = len (arr) sortSpecialPrimes(arr, n); # This code is contributed by phasing17 |
C#
// C# implementation of the above approach using System; using System.Collections.Generic; using System.Linq; class GFG{ // Function for the Sieve of Eratosthenes static void sieveOfEratosthenes( bool []prime, int n) { prime[0] = 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 // greater than or equal to the // square of it numbers which are // multiple of p and are less than // p^2 are already been marked. for ( int i = p * p; i <= n; i += p) prime[i] = false ; } } } // Function to sort the special primes // in their relative positions static void sortSpecialPrimes( int []arr, int n) { // Maximum element from the array int maxVal = arr.Max(); // prime[i] will be true if i is a prime bool []prime = new bool [maxVal + 1]; for ( int i = 0; i < prime.Length; i++) prime[i] = true ; sieveOfEratosthenes(prime, maxVal); // To store the special primes // from the array List< int > list = new List< int >(); for ( int i = 0; i < n; i++) { // If current element is a special prime if (prime[arr[i]] && prime[arr[i] - 2]) { // Add it to the List // and set arr[i] to -1 list.Add(arr[i]); arr[i] = -1; } } // Sort the special primes list.Sort(); int j = 0; for ( int i = 0; i < n; i++) { // Position of a special prime if (arr[i] == -1) Console.Write(list[j++] + " " ); else Console.Write(arr[i] + " " ); } } // Driver code public static void Main(String[] args) { int []arr = { 31, 5, 2, 1, 7 }; int n = arr.Length; sortSpecialPrimes(arr, n); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the above approach // Function for the Sieve of Eratosthenes function sieveOfEratosthenes(prime, n) { prime[0] = prime[1] = false ; for (let 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 // greater than or equal to the // square of it numbers which are // multiple of p and are less than // p^2 are already been marked. for (let i = p * p; i <= n; i += p) prime[i] = false ; } } } // Function to sort the special primes // in their relative positions function sortSpecialPrimes(arr, n) { // Maximum element from the array let maxVal = Math.max(...arr); // prime[i] will be true if i is a prime let prime = Array.from( {length: maxVal + 1}, (_, i) => 0); for (let i = 0; i < prime.length; i++) prime[i] = true ; sieveOfEratosthenes(prime, maxVal); // To store the special primes // from the array let list = []; for (let i = 0; i < n; i++) { // If current element is a special prime if (prime[arr[i]] && prime[arr[i] - 2]) { // Add it to the List // and set arr[i] to -1 list.push(arr[i]); arr[i] = -1; } } // Sort the special primes list.sort((a, b) => a - b); let j = 0; for (let i = 0; i < n; i++) { // Position of a special prime if (arr[i] == -1) document.write(list[j++] + " " ); else document.write(arr[i] + " " ); } } // Driver Code let arr = [ 31, 5, 2, 1, 7 ]; let n = arr.length; sortSpecialPrimes(arr, n); // This code is contributed by target_2 </script> |
Output:
5 7 2 1 31
Time Complexity: O(n * log n)
Auxiliary Space: O(n)
Contact Us