[Baekjoon] 2609 최대공약수와 최소공배수(파이썬/자바스크립트/NodeJS)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

2609번: 최대공약수와 최소공배수

---

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6
72

---

정답 코드

재귀 활용
파이썬 Ver.

import sys


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(a, b), lcm(a, b), sep="\n")

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const a = input[0];
const b = input[1];

const answer1 = (a, b) => {
    console.log('answer1');

    const gcd = (a, b) => {
        if (b === 0) return a;

        const r = a % b;
        return gcd(b, r);
    };

    const lcm = (a, b) => {
        return parseInt((a * b) / gcd(a, b));
    };

    console.log(gcd(a, b) + '\n' + lcm(a, b));
};

answer1(a, b);

 

while 반복문 활용
파이썬 Ver.

import sys


def gcd(a, b):
    while (b != 0):
       a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(a, b), lcm(a, b), sep="\n")

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const a = input[0];
const b = input[1];

const answer2 = (a, b) => {
    console.log('answer2');

    const gcd = (a, b) => {
        while (b != 0) {
            r = a % b;
            a = b;
            b = r;
        }

        return a;
    };

    const lcm = (a, b) => {
        return parseInt((a * b) / gcd(a, b));
    };

    console.log(gcd(a, b) + '\n' + lcm(a, b));
};
answer2(a, b);

math 모듈 활용

import sys
import math

a, b = map(int, sys.stdin.readline().rstrip().split())


def answer2(a, b):
    print(math.gcd(a, b), math.lcm(a, b), sep="\n")


answer2(a, b)

---

문제 풀이

 최대공약수 문제는 유클리드 호제법을 활용하면 쉽게 풀 수 있다.

 

유클리드 호제법
2개의 자연수 a와 b가 주어질 때 a > b이고 a를 b로 나눈 나머지를 r이라 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 

 위 문장을 코드로 구현한 것이 위의 정답 코드들이다. 크게 재귀 함수를 이용하거나 while 반복문을 활용하는 방법이 있다. 

 최소공배수는 2개의 자연수 a와 b의 곱에 a와 b의 최대공약수를 나눈 값과 같다는 성질을 이용하면 구할 수 있다.

 파이썬 3.9버전 이상부터는 math 모듈에 최대공약수(gcd)와 최소공배수(lcm)을 구하는 메서드가 내장되어 있어 매우 간단하게 두 값을 구할 수 있다.

---

함께 보기

https://velog.io/@junyp1/%EB%B0%B1%EC%A4%80-2609-Python-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%99%80-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

백준 - 2609 (Python) - 최대공약수와 최소공배수