Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Basics

GCD and LCM

Easy · Basics · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Given two positive integers a and b, print their GCD and LCM.

Input

One line with a b.

Output

Print gcd lcm separated by a space.

Constraints

Use the Euclidean algorithm. LCM can be as large as 10^18 — compute it as a / gcd * b with 64-bit integers.

Example 1

Input

12 18

Output

6 36

Example 2

Input

7 5

Output

1 35

Hints

  1. Euclid: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.
  2. lcm = a / gcd * b. Divide first so the intermediate value stays small, and use 64-bit integers.

Approach

The Euclidean algorithm repeatedly replaces (a, b) with (b, a mod b) until b is 0; the remaining a is the GCD. Then lcm(a, b) = a / gcd × b. Dividing before multiplying keeps the intermediate value at most 10^18, which fits in a 64-bit integer.

Complexity: O(log min(a, b)) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    long long a, b;
    cin >> a >> b;
    long long g = gcd(a, b);
    cout << g << " " << a / g * b << "\n";
    return 0;
}

Python solution

from math import gcd

a, b = map(int, input().split())
g = gcd(a, b)
print(g, a // g * b)

Java solution

import java.util.*;

public class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong();
        long g = gcd(a, b);
        System.out.println(g + " " + (a / g * b));
    }
}

Solve GCD and LCM online · All practice problems