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
- 1 ≤ a, b ≤ 10^9
Use the Euclidean algorithm. LCM can be as large as 10^18 — compute it as
a / gcd * bwith 64-bit integers.
Example 1
Input
12 18
Output
6 36
Example 2
Input
7 5
Output
1 35
Hints
- Euclid: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.
- 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));
}
}