GCD and LCM

Lab C Intermediate 20 points

Read two positive integers and print their GCD (Euclid's algorithm) and LCM.

Input

Two integers.

Output

Two lines.

Example

Input

12 18

Output

6
36

Sample input available Sample output available

Editor

Hints

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

Divide before multiplying to avoid overflow.

Solution explanation

Euclid's algorithm needs very few steps even for large numbers.

Show solution

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int x = a, y = b;
    while (y != 0) {
        int t = x % y;
        x = y;
        y = t;
    }
    printf("%d\n%d\n", x, a / x * b);
    return 0;
}

Output

Answer