[Baekjoon Online Judge] 백준 2609번 최대공약수와 최소공배수(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2609번 최대공약수와 최소공배수

(Python)

(글쓴날 : 2020.03.23)

 

---

* Baekjoon Online Judge, 백준 2609번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2609번 최대공약수와 최소공배수

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2609

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

---

2) 풀이 과정

주어진 두 자연수의 최대공약수와 최소공배수를 구하는 문제입니다.

 

이 문제를 풀기 위해 사용되는 대표적인 알고리즘이 하나 있는데, 바로 두 자연수의 최대공약수를 구하는 알고리즘의 하나인 유클리드 호제법입니다.

 

* 유클리드 호제법이 궁금하시다면 ☞ [Algorithm] 유클리드 호제법

 

물론, 유클리드 호제법을 사용하지 않고도 문제를 풀 순 있으므로, 저의 경우 제가 생각나는 의식의 흐름대로 문제를 먼저 풀어본 뒤, 그 후에 유클리드 호제법을 적용해 풀어보았습니다.

 

밑의 코드에 유클리드 호제법을 적용하지 않은 경우와 적용한 경우 둘 다 있으니 한번 비교해 보시면 좋을 것 같습니다.

---

3) 코드

 

* Python 코드(유클리드 호제법 미적용)

import sys
input = sys.stdin.readline
 
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()

---

* Python 코드(유클리드 호제법 적용)

import sys
input = sys.stdin.readline
 
 
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, a * b // g, sep="\n")

---