Сортировать заданный массив в порядке убывания в соответствии с наибольшей степенью простых множителей

Опубликовано: 20 Сентября, 2022

Дан массив arr[] размера N . Задача состоит в том, чтобы отсортировать элементы в arr[] по их наивысшей степени выражения в порядке убывания. Наивысшая степень числа определяется как максимальное значение, в котором оно может быть выражено как мощность его множителей.

Примечание:

  • Если числа имеют одинаковую степень выраженности, элемент, стоящий первым в исходном массиве, будет первым в отсортированном массиве.
  • Если два числа имеют одинаковую наивысшую степень, следует использовать подход «первым пришел – первым обслужен».

Примеры:

Input: arr[] = {81, 25, 27, 32, 51}
Output: [32, 81, 27, 25, 51]
Explanation: After prime factorization
81 can be represented as 811, 92, or 34. For the highest degree of expression, choose (3)4 because 4 is greater than 2 and 1.
25 can be represented as 52.
27 can be represented as 33.
32 can be represented as 25. 
51 can be represented as 511.
Now, sort them in descending order based on their power.
Therefore, 32 comes first since 25 has the highest power, followed by 81, 27, 25, and finally 51 with a power of 1.

Input: arr[] = {23, 6}
Output: [23, 6]
Explanation: Since 23 and 6 both have the same power(1), we print 23 which comes first, followed by 6.

Подход : Эту проблему можно решить с помощью простой факторизации. Выполните следующие шаги, чтобы решить данную проблему.

  • Наивысшую степень числа можно получить, разбив его на произведение простых множителей.
  • Выберите фактор, который имеет наибольшую мощность среди этих факторов.
  • Сохраните наибольшую степень числа вместе с этим числом в паре и отсортируйте эту пару на основе наибольшей мощности ее множителей.
  • Предварительно вычислите все простые числа до 10 ^ 5, используя метод решета Эратосфена.
  • Для каждого числа в массиве найдите все множители этого числа и сохраните наивысшую степень его множителя вместе с этим числом в векторе пары целых чисел.
  • Отсортируйте эту пару по убыванию на основе второго элемента (наивысший порядок выражения).

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N 1,5 *log(K)), где K — максимальный элемент в массиве.
Вспомогательное пространство : O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ