최대공약수와 최소공배수

문제

최대공약수와 최소공배수

풀이

유클리드 호제법을 이용해 최대공약수를 구한 뒤, 두 수의 곱을 최대공약수로 나눠 최소공배수를 구하면 됩니다.

코드

Python

import sys
 
input = lambda: sys.stdin.readline().rstrip()
 
a, b = map(int, input().split())
 
 
def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a
 
 
g = gcd(a, b)
print(g)
print(a * b // g)

C++

#include <bits/stdc++.h>
using namespace std;
 
int gcd(int a, int b) {
    while (b != 0) {
        a %= b;
        swap(a, b);
    }
    return a;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int a, b;
    cin >> a >> b;
    int g = gcd(a, b);
 
    cout << g << '\n' << a * b / g;
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer tk = new StringTokenizer(br.readLine());
 
        int a = Integer.parseInt(tk.nextToken()), b = Integer.parseInt(tk.nextToken());
        int g = gcd(a, b);
        bw.write(g + "\n" + a * b / g);
 
        bw.close();
    }
}