GCD and LCM
GCD and LCM
Given two positive integers a and b, compute and print their Greatest Common Divisor (GCD) and Least Common Multiple (LCM). The GCD of two integers is the largest positive integer that divides both of them without a remainder. The LCM is the smallest positive integer that is divisible by both a and b. Example: a=12, b=18 → GCD=6, LCM=36
Input format — only if your code reads from stdin
Input format: - A single line with two space-separated integers a and b Output: - First line: GCD(a, b) - Second line: LCM(a, b)
Approach
Use the Euclidean algorithm for GCD: GCD(a, b) = GCD(b, a % b), base case GCD(a, 0) = a. For LCM, use the identity LCM(a, b) = (a / GCD(a, b)) * b — divide first to avoid integer overflow.
Input
Output
- •
1 ≤ a, b ≤ 10^9
More Algorithms problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards