Java: Greatest common divisor and least common multiple

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) and static 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));
        }
    }
}

Lesson: Methods →