Given a positive integer, A. The task is to find two numbers B and C such that their product is A and their GCD should be maximum.
Examples:
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.
Approach: This problem can be solved by generating Prime factors of A. To maximize GCD the only possible way is to choose different prime factors so that product of them would give the maximum GCD. Follow the steps given below to solve the problem.
- Create a function say, primeFactors() to find all the prime factors of a number.
- Firstly call primeFactors() and pass A and an array is passed by reference to store all prime factors in a sorted manner.
- Iterate over the prime factor array, and distribute all the factors of A to B and C alternatively such that,
- B = primefactor[0] * primefactor[2] * primefactor[4] – – – and so on.
- C = primefactor[1] * primefactor[3] * primefactor[5] – – – and so on.
- Output the numbers B and C separated by space.
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.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to stores prime factors// of a number in a vector.void primeFactors(int A, vector<int>& prime){ while (A % 2 == 0) { prime.push_back(2); A = A / 2; } for (int i = 3; i <= sqrt(A); i += 2) { while (A % i == 0) { prime.push_back(i); A = A / i; } } if (A > 2) prime.push_back(A);}// Find the numbers B and C// such that gcd(B, C) is max// and product is A.void maxPairGCD(int A){ // Vector to store prime factors vector<int> prime; primeFactors(A, prime); int B = 1, C = 1; int temp = 0; for (int i = 0; i < prime.size(); i++) { if (temp == 0) B *= prime[i]; else C *= prime[i]; temp = temp ^ 1; } cout << B << " " << C;}// Driver codeint main(){ int A = 72; // Function Call maxPairGCD(A); return 0;} |
Java
// Java program to implement// the above approachimport java.util.ArrayList;class GFG { // Function to stores prime factors // of a number in a vector. static void primeFactors(int A, ArrayList<Integer> prime) { while (A % 2 == 0) { prime.add(2); A = A / 2; } for (int i = 3; i <= Math.sqrt(A); i += 2) { while (A % i == 0) { prime.add(i); A = A / i; } } if (A > 2) prime.add(A); } // Find the numbers B and C // such that gcd(B, C) is max // and product is A. static void maxPairGCD(int A) { // Vector to store prime factors ArrayList<Integer> prime = new ArrayList<Integer>(); primeFactors(A, prime); int B = 1, C = 1; int temp = 0; for (int i = 0; i < prime.size(); i++) { if (temp == 0) B *= prime.get(i); else C *= prime.get(i); temp = temp ^ 1; } System.out.println(B + " " + C); } // Driver code public static void main(String args[]) { int A = 72; // Function Call maxPairGCD(A); }}// This code is contributed by Saurabh Jaiswal |
Python3
# Python 3 program for above approachimport math# Function to stores prime factors# of a number in a vector.def primeFactors(A, prime): while (A % 2 == 0): prime.append(2) A = A / 2 for i in range(3, int(math.sqrt(A)) + 1, 2): while (A % i == 0): prime.append(i) A = A / i if (A > 2): prime.append(A)# Find the numbers B and C# such that gcd(B, C) is max# and product is A.def maxPairGCD(A): # Vector to store prime factors prime = [] primeFactors(A, prime) B = 1 C = 1 temp = 0 for i in range(len(prime)): if (temp == 0): B *= prime[i] else: C *= prime[i] temp = temp ^ 1 print(B, C)# Driver codeif __name__ == "__main__": A = 72 # Function Call maxPairGCD(A) # This code is contributed by ukasp. |
C#
// C# program to implement// the above approachusing System;using System.Collections;class GFG{ // Function to stores prime factors // of a number in a vector. static void primeFactors(int A, ArrayList prime) { while (A % 2 == 0) { prime.Add(2); A = A / 2; } for (int i = 3; i <= Math.Sqrt(A); i += 2) { while (A % i == 0) { prime.Add(i); A = A / i; } } if (A > 2) prime.Add(A); } // Find the numbers B and C // such that gcd(B, C) is max // and product is A. static void maxPairGCD(int A) { // Vector to store prime factors ArrayList prime = new ArrayList(); primeFactors(A, prime); int B = 1, C = 1; int temp = 0; for (int i = 0; i < prime.Count; i++) { if (temp == 0) B *= (int)prime[i]; else C *= (int)prime[i]; temp = temp ^ 1; } Console.Write(B + " " + C); } // Driver code public static void Main() { int A = 72; // Function Call maxPairGCD(A); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to stores prime factors // of a number in a vector. function primeFactors(A, prime) { while (A % 2 == 0) { prime.push(2); A = A / 2; } for (let i = 3; i <= Math.sqrt(A); i += 2) { while (A % i == 0) { prime.push(i); A = A / i; } } if (A > 2) prime.push(A); return prime; } // Find the numbers B and C // such that gcd(B, C) is max // and product is A. function maxPairGCD(A) { // Vector to store prime factors let prime = []; prime = primeFactors(A, prime); let B = 1, C = 1; let temp = 0; for (let i = 0; i < prime.length; i++) { if (temp == 0) B *= prime[i]; else C *= prime[i]; temp = temp ^ 1; } document.write(B + " " + C) } // Driver code let A = 72; // Function Call maxPairGCD(A); // This code is contributed by Potta Lokesh </script> |
Output
12 6
Time Complexity: O(Sqrt(A) )
Auxiliary Space: O(log(A))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
