Find the greatest common divisor and the least common multiple of pairs of numbers.
What to build
Two small functions, where the second is built on the first.
Requirements
- Write
gcd(a, b)using recursion. - Write
lcm(a, b)usinggcd. - For each input line, print
gcd G lcm L.
Input
Several lines. Each has two whole numbers separated by a space.
Output
One line for each input line.
Constraints
Each number is from 1 to 100000.
Example
Input:
12 18
Output:
gcd 6 lcm 36
Why it works
Any number that divides both a and b also divides a % b, so the pair can be replaced by a smaller pair without changing the answer. Each call shrinks the numbers, so the base case is always reached.
Examples
Example 1 · Input
12 18
Expected output
gcd 6 lcm 36
Example 2 · Input
7 5
Expected output
gcd 1 lcm 35
Hints
Hint 1
Euclid's rule is gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.
Hint 2
Write gcd as a recursive function, with b === 0 as the base case.
Hint 3
lcm(a, b) is a * b / gcd(a, b).
Solution
Show one correct solution (try it yourself first)
function gcd(a, b) {
if (b === 0) {
return a;
}
return gcd(b, a % b);
}
function lcm(a, b) {
return (a * b) / gcd(a, b);
}
let line = prompt();
while (line !== null) {
const [a, b] = line.split(" ").map(Number);
console.log(`gcd ${gcd(a, b)} lcm ${lcm(a, b)}`);
line = prompt();
}