[Python, Javascript] 백준 온라인 저지 2609번

실버 LV5 https://www.acmicpc.net/problem/2609

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

 

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

 

 

[Python]

 

풀이 방법:

 

두 자연수의 최대공약수를 구하는 방법으로는 유클리드 호제법이 있다.

호제법이란 주어진 두 수로 서로 다른 수를 나누어 원하는 결과를 얻는 방법을 의미한다.

 

유클리드 호제법

어떤 자연수 a, b가 있을 때 (a > b), 두 수의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.

python code

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)
 
## 최대공약수 = gcd(자연수1, 자연수2)

 

정답:

 

1) 유클리드 호제법 미사용

a, b = map(int, input().split())
 
for i in range(b, 0, -1):
    if a % i == 0 and b % i == 0:
        print(i) # 최대공약수
        print(i * a // i * b // i) # 최소공배수
        exit()

 

2) 유클리드 호제법 사용

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

a, b = map(int, input().split())
g = gcd(a, b) # 최대공약수

print(g)
print(a * b // g) # 최소공배수

 

 

 

[Javascript]

 

풀이 방법:

 

두 자연수를 우선 비교하여 큰 수와 작은 수를 가름한다.

while문으로 큰 수와 작은 수의 최대공약수를 구한다.

 

 

정답:

const fs = require('fs');
const [a, b] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(v => parseInt(v));

let [bigger, smaller] = a > b ? [a, b] : [b, a];
let gcd;
while (true) {
    const rest = bigger % smaller;
    if (rest === 0) {
        gcd = smaller;
        break;
    }
    
    bigger = smaller;
    smaller = rest;
}

console.log(gcd);
console.log(gcd * (a / gcd) * (b / gcd));