Write a short recursive method, then build a second method on top of it.
What to build
A program that prints the gcd and the lcm of pairs of numbers.
Requirements
- Write a recursive
static long gcd(long a, long b)andstatic long lcm(long a, long b). - For each pair print
gcd(A, B) = G, lcm = L.
Input
Line 1: n. Then n lines of two whole numbers.
Output
n lines.
Constraints
1 ≤ n ≤ 100; 1 ≤ A, B ≤ 10^9.
Example
Input:
2
12 18
7 5
Output:
gcd(12, 18) = 6, lcm = 36
gcd(7, 5) = 1, lcm = 35
Why it works
Euclid's algorithm shrinks the pair quickly until the remainder is 0, and dividing by the gcd before multiplying keeps the lcm within a long, since it is at most 10^18.
Examples
Example 1 · Input
2 12 18 7 5
Expected output
gcd(12, 18) = 6, lcm = 36 gcd(7, 5) = 1, lcm = 35
Example 2 · Input
1 100 10
Expected output
gcd(100, 10) = 10, lcm = 100
Hints
Hint 1
Euclid: gcd(a, b) is a when b is 0, and gcd(b, a % b) otherwise.
Hint 2
lcm(a, b) = a / gcd(a, b) * b; divide first so the product stays in range.
Solution
Show one correct solution (try it yourself first)
import java.util.Scanner;
public class Main {
static long gcd(long a, long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
static long lcm(long a, long b) {
return a / gcd(a, b) * b;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int i = 0; i < n; i++) {
long a = in.nextLong();
long b = in.nextLong();
System.out.println("gcd(" + a + ", " + b + ") = " + gcd(a, b) + ", lcm = " + lcm(a, b));
}
}
}