Given gcd G and lcm L. The task is to print any pair which has gcd G and lcm L.
Examples:
Input: G = 3, L = 12 Output: 3, 12 Input: G = 1, L = 10 Output: 1, 10
A normal solution will be to perform iteration over all the factor pairs of g*l and check if any pair has gcd g and lcm as l. If they have, then the pair will be the answer.
Below is the implementation of the above approach.
C++
// C++ program to print any pair// with a given gcd G and lcm L#include <bits/stdc++.h>using namespace std;// Function to print the pairsvoid printPair(int g, int l){ int n = g * l; // iterate over all factor pairs for (int i = 1; i * i <= n; i++) { // check if a factor if (n % i == 0) { int first = i; int second = n / i; // find gcd int gcd = __gcd(first, second); // check if gcd is same as given g // and lcm is same as lcm l if (gcd == g && l % first == 0 && l % second == 0) { cout << first << " " << second; return; } } }}// Driver Codeint main(){ int g = 3, l = 12; printPair(g, l); return 0;} |
Java
// Java program to print any pair // with a given gcd G and lcm L import java.math.BigInteger;class GFG {// Function to print the pairs static void printPair(int g, int l) { int n = g * l; // iterate over all factor pairs for (int i = 1; i * i <= n; i++) { // check if a factor if (n % i == 0) { int first = i; int second = n / i; // find gcd int gcd = __gcd(first, second); // check if gcd is same as given g // and lcm is same as lcm l if (gcd == g && l % first == 0 && l % second == 0) { System.out.println(first + " " + second); return; } } } }//Function return GCD of two given number private static int __gcd(int a, int b) { // there's a better way to do this. I forget. BigInteger b1 = new BigInteger("" + a); BigInteger b2 = new BigInteger("" + b); BigInteger gcd = b1.gcd(b2); return gcd.intValue(); }// Driver function public static void main(String[] args) { int g = 3, l = 12; printPair(g, l); }}// This code is contributed by RAJPUT-JI |
Python3
# Python program to print any pair # with a given gcd G and lcm L # Function to print the pairs def printPair(g, l): n = g * l; # iterate over all factor pairs for i in range(1,n+1): # check if a factor if (n % i == 0): first = i; second = n // i; # find gcd gcd = __gcd(first, second); # check if gcd is same as given g # and lcm is same as lcm l if (gcd == g and l % first == 0 and l % second == 0): print(first , " " , second); return; # Function return GCD of two given number def __gcd(a, b): if(b==0): return a; else: return __gcd(b, a % b); # Driver Code g = 3;l = 12; printPair(g, l);# This code is contributed by Princi Singh |
C#
// C# program to print any pair // with a given gcd G and lcm L using System;public class GFG {// Function to print the pairs static void printPair(int g, int l) { int n = g * l; // iterate over all factor pairs for (int i = 1; i * i <= n; i++) { // check if a factor if (n % i == 0) { int first = i; int second = n / i; // find gcd int gcd = __gcd(first, second); // check if gcd is same as given g // and lcm is same as lcm l if (gcd == g && l % first == 0 && l % second == 0) { Console.WriteLine(first + " " + second); return; } } } }//Function return GCD of two given number private static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); }// Driver function public static void Main() { int g = 3, l = 12; printPair(g, l); }}// This code is contributed by RAJPUT-JI |
PHP
<?php// PHP program to print any pair // with a given gcd G and lcm L // Function to print the pairs function printPair($g, $l) { $n = $g * $l; // iterate over all factor pairs for ($i = 1; $i * $i <= $n; $i++) { // check if a factor if ($n % $i == 0) { $first = $i; $second = (int)$n / $i; // find gcd $gcd = __gcd($first, $second); // check if gcd is same as given g // and lcm is same as lcm l if ($gcd == $g && $l % $first == 0 && $l % $second == 0) { echo $first , " " , $second; return; } } } } // Function return GCD of two given number function __gcd($a, $b){ return $b == 0 ? $a : __gcd($b, $a % $b); } // Driver Code $g = 3;$l = 12; printPair($g, $l); // This code is contributed by ajit |
Javascript
<script>// javascript program to print any pair // with a given gcd G and lcm L // Function to print the pairs function printPair(g , l) { var n = g * l; // iterate over all factor pairs for (i = 1; i * i <= n; i++) { // check if a factor if (n % i == 0) { var first = i; var second = n / i; // find gcd var gcd = __gcd(first, second); // check if gcd is same as given g // and lcm is same as lcm l if (gcd == g && l % first == 0 && l % second == 0) { document.write(first + " " + second); return; } } } } // Function return GCD of two given number function __gcd(a, b){ return b == 0 ? a : __gcd(b, a % b); } // Driver function var g = 3, l = 12; printPair(g, l);// This code is contributed by aashish1995</script> |
Output:
3 12
Time Complexity: O(sqrt(g*l))
Auxiliary Space: O(1)
An efficient solution will be to observe that the lcm is always divisible by gcd, hence the answer can be obtained in O(1). One of the numbers will be the gcd G itself and the other will be the lcm L.
Below is the implementation of the above approach.
C++
// C++ program to print any pair// with a given gcd G and lcm L#include <iostream>using namespace std;// Function to print the pairsvoid printPair(int g, int l){ cout << g << " " << l;}// Driver Codeint main(){ int g = 3, l = 12; printPair(g, l); return 0;} |
Java
// Java program to print any pair// with a given gcd G and lcm Limport java.io.*;class GFG { // Function to print the pairs static void printPair(int g, int l){ System.out.print( g + " " + l);}// Driver Code public static void main (String[] args) { int g = 3, l = 12; printPair(g, l); }}// This code is contributed by inder_verma. |
Python 3
# Python 3 program to print any pair# with a given gcd G and lcm L# Function to print the pairsdef printPair(g, l): print(g, l)# Driver Codeg = 3; l = 12;printPair(g, l);# This code is contributed # by Akanksha Rai |
C#
// C# program to print any pair // with a given gcd G and lcm L using System;class GFG { // Function to print the pairs static void printPair(int g, int l) { Console.Write( g + " " + l); } // Driver Code public static void Main () { int g = 3, l = 12; printPair(g, l); } } // This code is contributed // by Subhadeep |
PHP
<?php// PHP program to print any pair // with a given gcd G and lcm L // Function to print the pairs function printPair($g, $l) { echo $g ; echo (" "); echo $l; } // Driver Code $g = 3;$l = 12; printPair($g, $l); // This code is contributed // by Shivi_Aggarwal?> |
Javascript
<script>// javascript program to print any pair// with a given gcd G and lcm L// Function to print the pairs function printPair(g, l) { document.write(g + " " + l); } // Driver Code var g = 3, l = 12; printPair(g, l);// This code is contributed by gauravrajput1</script> |
Output:
3 12
Time Complexity: O(1)
Auxiliary Space: O(1)
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!
