{ }codelper
GCDdefining functionsoverflowP0037

GCD and LCM

Two positive integers a and b are given on one line, separated by a space.
Print their greatest common divisor and least common multiple on one line, separated by a single space.

Input
1 ≤ a, b ≤ 10^12.
The LCM does not exceed 10^15.
Output
gcd lcm
Example 1 · stdin
12 18
stdout
6 36
Example 2 · stdin
987000000000 977000000000
stdout
1000000000 964299000000000
main.py
Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

Find the GCD with Euclid's algorithm (a, b = b, a % b until b is 0), and compute the LCM as a / g * b: divide first, multiply second.
Multiplying first (a * b / g) makes a*b ≈ 9.6×10^23 in example 2, which overflows the 64-bit long of C, C++, Java and C# (about 9.2×10^18), and pushes JavaScript, TypeScript and Craykon past 2^53 so the last digits go wrong.
Only Python, with unbounded integers, gets it right either way.
10^12 does not fit a 32-bit int (about 2.1 billion), so C-family languages read into long/long long from the start.
Built-ins: Python math.gcd, C++ std::gcd (<numeric>), C# BigInteger.GreatestCommonDivisor.
In Craykon, define the function as gcd(a, b) { … return a; }, and since / divides into decimals, take the quotient with Mathf.Quot(a, g).

Pythonmain.py · 9 lines
def gcd(a, b):    while b:        a, b = b, a % b    return a  a, b = map(int, input().split())g = gcd(a, b)print(g, a // g * b)
JavaScriptmain.js · 9 lines
const [a, b] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); function gcd(a, b) {  while (b !== 0) [a, b] = [b, a % b];  return a;} const g = gcd(a, b);console.log(`${g} ${(a / g) * b}`);
TypeScriptmain.ts · 10 lines
import { readFileSync } from "node:fs";const [a, b]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); function gcd(a: number, b: number): number {  while (b !== 0) [a, b] = [b, a % b];  return a;} const g = gcd(a, b);console.log(`${g} ${(a / g) * b}`);
JavaMain.java · 19 lines
import java.util.Scanner; public class Main {    static long gcd(long a, long b) {        while (b != 0) {            long t = a % b;            a = b;            b = t;        }        return a;    }     public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        long a = sc.nextLong(), b = sc.nextLong();        long g = gcd(a, b);        System.out.println(g + " " + (a / g * b));    }}
C#Main.cs · 20 lines
using System; class Program{    static long Gcd(long a, long b)    {        while (b != 0)        {            (a, b) = (b, a % b);        }        return a;    }     static void Main()    {        long[] v = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse);        long g = Gcd(v[0], v[1]);        Console.WriteLine($"{g} {v[0] / g * v[1]}");    }}
C++main.cpp · 9 lines
#include <iostream>#include <numeric> int main() {    long long a, b;    std::cin >> a >> b;    long long g = std::gcd(a, b);    std::cout << g << ' ' << a / g * b << '\n';}
Cmain.c · 18 lines
#include <stdio.h> long long gcd(long long a, long long b) {    while (b != 0) {        long long t = a % b;        a = b;        b = t;    }    return a;} int main(void) {    long long a, b;    scanf("%lld %lld", &a, &b);    long long g = gcd(a, b);    printf("%lld %lld\n", g, a / g * b);    return 0;}
Craykonmain.cray · 16 lines
최대공약수(a, b){    while (b != 0)    {        t = a % b;        a = b;        b = t;    }    return a;} 수들 = Console.ReadNumbers();a = 수들[0];b = 수들[1];g = 최대공약수(a, b);Console.WriteLine(g + " " + Mathf.Quot(a, g) * b);