Найдите два числа B и C, произведение которых равно A, а НОД максимален.
Учитывая положительное целое число, A . Задача состоит в том, чтобы найти два числа B и C так что их произведение равно A , а их НОД должен быть максимальным.
Примеры:
Input: A = 72
Output: 12 6
Explanation: The product of 12 and 6 is 72 and GCD(12, 6) is 6 which is maximum possible.Input: A = 54
Output: 6 9
Explanation: The product of 6 and 9 is 54, gcd(6, 9) is 3 which is maximum possible.
Подход: Эта проблема может быть решена путем генерации простых множителей A. Единственный возможный способ максимизировать НОД — выбрать различные простые множители так, чтобы произведение их давало максимальный НОД . Следуйте инструкциям ниже, чтобы решить проблему.
- Создайте функцию, скажем, primeFactors() , чтобы найти все простые множители числа.
- Сначала вызовите PrimeFactors() и передайте A , и массив будет передан по ссылке для хранения всех простых факторов в отсортированном виде.
- Выполните итерацию по массиву простых множителей и попеременно распределите все множители от A до B и C так, чтобы
- B = основной фактор[0] * основной фактор[2] * основной фактор[4] – – – и так далее.
- C = основной фактор[1] * основной фактор[3] * основной фактор[5] – – – и так далее.
- Выведите числа B и C через пробел.
For Example: N = 72
Prime Factorization of 72 = 2 * 2 * 2 * 3 * 3.
primefactor[] = {2, 2, 2, 3, 3}
B = primefactor[0] * primefactor[2] * primefactor[4] => 2 * 2 * 3 = 12.
C = primefactor[1] * primefactor[3] => 2 * 3 = 6.
Hence, B = 12 and C = 6.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(Sqrt(A))
Вспомогательное пространство: O(log(A))