GCD and LCM of Two Numbers

Given two positive integers a and b, compute their greatest common divisor (GCD) and least common multiple (LCM). The GCD is the largest integer that divides both a and b without a remainder. The LCM is the smallest positive integer that is divisible by both a and b. Print both values separated by a single space.

Input: A single line containing two space-separated integers a and b. Output: Print two space-separated integers: the GCD of a and b, followed by the LCM of a and b.

1 <= a, b <= 10^9

Euclid's algorithm is one of the OLDEST known algorithms in mathematics (dating back over 2000 years) and remains the standard, optimal approach - a great fact to mention showing appreciation for foundational algorithmic history.

Find the greatest common divisor and least common multiple of two numbers. Brute force: Check every integer from 1 up to min(a,b) to find the largest common divisor directly - this costs O(min(a,b)), far too slow for values up to 10^9. Optimised: Euclid's algorithm exploits the mathematical fact that gcd(a,b) = gcd(b, a mod b) - each step reduces the numbers roughly by a Fibonacci-like ratio, achieving the GCD in O(log(min(a,b))) steps instead of a linear scan; the LCM then follows directly from the GCD via a simple formula.

1. Use EUCLID'S ALGORITHM: gcd(a, b) = gcd(b, a mod b), with the base case gcd(a, 0) = a. 2. Once you have gcd(a, b), compute lcm(a, b) = (a / gcd(a, b)) * b - dividing BEFORE multiplying to reduce overflow risk. 3. Print both values.

Time: O(log(min(a,b))) - Euclid's algorithm converges very quickly. Space: O(1) - a small constant number of variables (or O(log(min(a,b))) stack frames if implemented recursively).

a and b may be equal, and either may be 1 (GCD=1, LCM=the other number). The LCM may exceed the 32-bit integer range for large a and b, so use 64-bit arithmetic throughout.

Be ready to derive the LCM formula from the GCD (lcm = a*b/gcd) and explain why dividing by the GCD FIRST (rather than multiplying a*b first, then dividing) reduces the risk of intermediate overflow.