Ordenar array dada en orden descendente según la potencia más alta de los factores primos

Dada una array arr[] de tamaño N . La tarea es ordenar los elementos en arr[] según su grado más alto de expresión , en orden descendente. El grado más alto de un número se define como el valor máximo en el que se puede expresar como la potencia de sus factores. 

Nota: 

• Si los números tienen el mismo grado de expresión, el elemento que aparece primero en la array original aparecerá primero en la array ordenada.
• Si dos números tienen el mismo grado más alto, entonces se debe usar el enfoque de orden de llegada.

Ejemplos:

Entrada : arr[] = {81, 25, 27, 32, 51}
Salida : [32, 81, 27, 25, 51]
Explicación : después de la descomposición en factores primos
, 81 se puede representar como 81 ¹ , 9 ² o 3 ⁴ . Para el grado más alto de expresión, elige (3) ⁴ porque 4 es mayor que 2 y 1.
25 se puede representar como 5 ^2.
27 se puede representar como 3 ³ .
32 se puede representar como 2 ⁵ . 
51 se puede representar como 51 ¹ .
Ahora, ordénelos en orden descendente según su poder.
Por lo tanto, 32 viene primero desde 2 ⁵tiene la potencia más alta, seguido de 81, 27, 25 y finalmente 51 con una potencia de 1.

Entrada : arr[] = {23, 6}
Salida : [23, 6]
Explicación : Dado que 23 y 6 tienen la misma potencia (1), imprimimos 23 que viene primero, seguido de 6.

Enfoque : Este problema se puede resolver utilizando la factorización prima . Siga los pasos a continuación para resolver el problema dado.

• La potencia más alta de un número se puede obtener descomponiéndolo en un producto de sus factores primos.
• Elija el factor que tiene la potencia más alta entre esos factores.
• Almacena la potencia más alta de un número junto con ese número en un par y ordena ese par según la potencia más alta de sus factores.
• Calcule previamente todos los números primos hasta 10 ^ 5 utilizando el método Tamiz de Eratóstenes .
• Para cada número en la array, encuentre todos los factores de ese número y almacene la potencia más alta de su factor junto con ese número en un vector de par de enteros.
• Ordene ese par en forma descendente según el segundo elemento (el orden más alto de expresión).

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
bitset<500001> Primes;
vector<int> Factors;
 
// Function to compute Sieve of Eratosthenes
void SieveOfEratosthenes(int n)
{
    Primes[0] = 1;
    for (int i = 3; i <= n; i += 2) {
        if (Primes[i / 2] == 0) {
            for (int j = 3 * i; j <= n; j += 2 * i)
                Primes[j / 2] = 1;
        }
    }
 
    for (int i = 2; i <= 500001; i++) {
        if (!Primes[i])
            Factors.push_back(i);
    }
}
 
// Compare function for sorting
bool compare(const pair<int, int>& a,
             const pair<int, int>& b)
{
    return a.second > b.second;
}
 
// Function to find any log(a) base b
int log_a_to_base_b(int a, int b)
{
    return log(a) / log(b);
}
 
// Function to find the Highest Power
// of K which divides N
int HighestPower(int N, int K)
{
    int start = 0, end = log_a_to_base_b(N, K);
    int ans = 0;
    while (start <= end) {
 
        int mid = start + (end - start) / 2;
        int temp = (int)(pow(K, mid));
 
        if (N % temp == 0) {
            ans = mid;
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
    return ans;
}
 
// Function to display N numbers
// on the basis of their Highest Order
// of Expression in descending order
void displayHighestOrder(int arr[], int N)
{
    vector<pair<int, int> > Nums;
 
    for (int i = 0; i < N; i++) {
 
        // The least power of a number
        // will always be 1 because
        // that number raised to
        // the power 1 is it itself
        int temp = 1;
        for (auto& Prime : Factors) {
 
            // The factor of a number greater than
            // its square root is the number itself
            // which is considered in temp
            if (Prime * Prime > arr[i])
                break;
            else if (arr[i] % Prime == 0)
                temp = max(
                    temp,
                    HighestPower(arr[i], Prime));
        }
        Nums.push_back(make_pair(arr[i], temp));
    }
 
    sort(Nums.begin(), Nums.end(), compare);
 
    for (int i = 0; i < N; i++) {
        cout << Nums[i].first << " ";
    }
    cout << endl;
}
 
// Driver Code
int main()
{
 
    SieveOfEratosthenes(500000);
 
    int arr[] = { 81, 25, 27, 32, 51 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    displayHighestOrder(arr, N);
 
    return 0;
}

# Python code for the above approach
import math as Math
 
Primes = [0] * 500001
Factors = []
 
# Function to compute Sieve of Eratosthenes
def SieveOfEratosthenes(n):
    Primes[0] = 1
    for i in range(3, n + 1, 2):
        if (Primes[i // 2] == 0):
            for j in range(3 * i, n + 1, 2 * i):
                Primes[j // 2] = 1
 
    for i in range(2, 500001) :
        if (not Primes[i]):
            Factors.append(i)
     
# Compare function for sorting
def compare(a, b):
    return b.second - a.second
 
# Function to find any log(a) base b
def log_a_to_base_b(a, b):
    return Math.log(a) / Math.log(b)
 
# Function to find the Highest Power
# of K which divides N
def HighestPower(N, K):
    start = 0
    end = log_a_to_base_b(N, K)
    ans = 0
    while (start <= end):
 
        mid = start + Math.floor((end - start) / 2)
        temp = (Math.pow(K, mid))
 
        if (N % temp == 0):
            ans = mid
            start = mid + 1
        else:
            end = mid - 1
    return ans
 
# Function to display N numbers
# on the basis of their Highest Order
# of Expression in descending order
def displayHighestOrder(arr, N):
    Nums = []
 
    for i in range(N):
 
        # The least power of a number
        # will always be 1 because
        # that number raised to
        # the power 1 is it itself
        temp = 1
        for Prime in Factors:
 
            # The factor of a number greater than
            # its square root is the number itself
            # which is considered in temp
            if (Prime * Prime > arr[i]):
                break
            elif (arr[i] % Prime == 0):
                temp = max( temp, HighestPower(arr[i], Prime))
        Nums.append({"first": arr[i], "second": temp})
     
 
    Nums = sorted(Nums, key=lambda l: l["second"], reverse=True)
 
    for i in range(N):
        print(Nums[i]["first"], end= " ")
    print('')
 
# Driver Code
SieveOfEratosthenes(500000)
arr = [81, 25, 27, 32, 51]
N = len(arr)
 
# Function Call
displayHighestOrder(arr, N)
 
# This code is contributed by gfgking.

<script>
      // JavaScript code for the above approach
      let Primes = new Array(500001);
      let Factors = [];
 
      // Function to compute Sieve of Eratosthenes
      function SieveOfEratosthenes(n) {
          Primes[0] = 1;
          for (let i = 3; i <= n; i += 2) {
              if (Primes[Math.floor(i / 2)] == 0) {
                  for (let j = 3 * i; j <= n; j += 2 * i)
                      Primes[Math.floor(j / 2)] = 1;
              }
          }
 
          for (let i = 2; i <= 500001; i++) {
              if (!Primes[i])
                  Factors.push(i);
          }
      }
 
      // Compare function for sorting
      function compare(a,
          b) {
          return b.second - a.second;
      }
 
      // Function to find any log(a) base b
      function log_a_to_base_b(a, b) {
          return Math.log(a) / Math.log(b);
      }
 
      // Function to find the Highest Power
      // of K which divides N
      function HighestPower(N, K) {
          let start = 0, end = log_a_to_base_b(N, K);
          let ans = 0;
          while (start <= end) {
 
              let mid = start + Math.floor((end - start) / 2);
              let temp = (Math.pow(K, mid));
 
              if (N % temp == 0) {
                  ans = mid;
                  start = mid + 1;
              }
              else {
                  end = mid - 1;
              }
          }
          return ans;
      }
 
      // Function to display N numbers
      // on the basis of their Highest Order
      // of Expression in descending order
      function displayHighestOrder(arr, N) {
          let Nums = [];
 
          for (let i = 0; i < N; i++) {
 
              // The least power of a number
              // will always be 1 because
              // that number raised to
              // the power 1 is it itself
              let temp = 1;
              for (Prime of Factors) {
 
                  // The factor of a number greater than
                  // its square root is the number itself
                  // which is considered in temp
                  if (Prime * Prime > arr[i])
                      break;
                  else if (arr[i] % Prime == 0)
                      temp = Math.max(
                          temp,
                          HighestPower(arr[i], Prime));
              }
              Nums.push({ first: arr[i], second: temp });
          }
 
          Nums.sort(compare)
 
          for (let i = 0; i < N; i++) {
              document.write(Nums[i].first + " ");
          }
          document.write('<br>')
      }
 
      // Driver Code
      SieveOfEratosthenes(500000);
      let arr = [81, 25, 27, 32, 51];
      let N = arr.length;
 
      // Function Call
      displayHighestOrder(arr, N);
 
// This code is contributed by Potta Lokesh
  </script>

32 81 27 25 51 

Complejidad de tiempo: O(N ^1.5 *log(K)), donde K es el elemento máximo en la array.
Espacio Auxiliar : O(1)