[파이썬] 단계별 백준 문제 풀기 - 2609 정수 (최대공약수와 최소공배수)

문제링크

문제

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

입력

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

출력

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

 

---

<<소스코드>> - 유클리드 호제법 이용

#a를 b로 나눈 나머지가 r이라면, b를 r로 나눈 나머지가 r2, r을 r2로 나눈 나머지가 r3... 
# 이를 계속하여 딱 떨어지기 직전의 나머지가 최대공약수가 된다.
# 두 수의 곱(a*b)과 최소공배수 * 최대공약수는 같다.


def gcd(a,b):
    if a%b == 0: #a를 b로 나눈 나머지가 0이면, b는 a의 약수이므로 b가 바로 최소공배수가 됨
        return b
    #나머지가 존재한다면, b를 (a를 b로 나눈 나머지)로 나누어준다. 나머지가 0으로 떨어지기 전까지 반복
    else: 
        return gcd(b,a%b) 

a, b = map(int,input().split())
r = gcd(a,b) 
m = (a*b)/r

print(r)
print(round(m)) #소수점 첫째자리까지 나와서 버림

<<math 모듈 활용>>

#math 모듈을 추가하면 math.gcd(a,b)를 통해 최대공약수를 구할 수 있다.
# a*b = gcd * lcm 을 이용하여, lcm도 구해준다.
import math
a, b = map(int,input().split())
lcm = round((a*b)/math.gcd(a,b))
print(math.gcd(a,b))
print(lcm)

<<결과값>>

24 18

6
72

---

유클리드 호제법을 알고 있으면 빠르게 풀 수 있다. 나는 몰라서 찾아봤다. 

최대공약수를 구하는 알고리즘이다.

a를 b로 나눈 나머지 r1이 있다면 r1으로 b를 나누어 r2의 나머지를 얻고, r1을 r2로 나눈 나머지를 r3 라고 한다면, r2를 r3로 나누어준다. 나머지가 0이 될 때까지 계속 나누었을때, 0이 되기 직전의 나머지가 최대공약수가 된다.

 

최대공약수와 최소공배수의 곱은 두 수의 곱과 같으므로 이를 이용하여 최소공배수도 구해주었다.

 

24, 18을 예제로 들었을 때 

24를 18로 나눈 나머지가 6이고, 18을 6으로 나누면 0으로 떨어지기때문에 직전의 나머지 6이 최대공약수가 되고

24 x 18 = 6 x 72 이기 때문에 최소공배수는 72가 된다.

 

math gcd 모듈을 이용해도 구할 수 있다!

import math 해주고, math.gcd(a,b)를 넣어주면 최대공약수를 더 빠르게 구할 수 있다....!

 

이를 알고 gcd 함수를 짜는 것도 한줄 코드 였지만 생각보다 어려웠다 크흑

 

b를 나누는 대상에 넣고, 그 나머지를 다시 나누는 값으로 넣고 -> 재귀냄새 킁킁

return gcd(b,a%b)