GCD (Euclid)

Lab Java Intermediate 20 points

Read two positive integers and print their greatest common divisor using Euclid's algorithm with a while loop, then their least common multiple.

Input

Two integers.

Output

Two lines: gcd, lcm.

Example

Input

12 18

Output

6
36

Sample input available Sample output available

Editor

Java

Hints

gcd(a, b) = gcd(b, a % b), until b is 0.

lcm = a / gcd * b.

Solution explanation

Euclid's algorithm is over 2000 years old and still the fastest simple way to get a GCD.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long x = a, y = b;
        while (y != 0) {
            long t = x % y;
            x = y;
            y = t;
        }
        System.out.println(x);
        System.out.println(a / x * b);
    }
}

Output

Answer