Find any pair with given GCD and LCM

0 0 6 minutes read

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 pairs
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) {
                cout << first << " " << second;
                return;
            }
        }
    }
}
 
// Driver Code
int 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 pairs
void printPair(int g, int l)
{
    cout << g << " " << l;
}
 
// Driver Code
int 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.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 pairs
def printPair(g, l):
    print(g, l)
 
# Driver Code
g = 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 zambiatek!