[Python] 백준 2609 최대공약수와 최소공배수

문제 바로가기

   문제분석   

# 유클리드 호제법으로 최대공약수를 구한 후, 그걸 힌트로 최소공배수를 구한다.

• a,b의 최대공약수 == b와 a%b의 최대공약수
• a%b가 0이 될 경우(나머지가 없이 a가 b로 딱 떨어진다는 것이므로) b가 최대공약수
• 최소공배수는 두 값의 곱/최대공약수

# 유클리드 호제법의 예

24 - 1 2 3 4 6 8 12 24	#24의 약수들
18 - 1 2 3 6 9 18	# 18의 약수들

   a = 24
   b = 18
   a, b = b , a % b

   24, 18 = 18, 6
   18, 6  = 6,  0
    -> 나머지가 0이 되었으니 나누는 수 6이 24와 18의 최대공약수

 

 

   문제풀이   

a, b = map(int, input().split())


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))
print(lcm(a, b))

# 두 수를 입력값으로 받는다.

# 최대공약수를 구하는 함수를 만든다.

• 최대공약수는 유클리드 호제법으로 각각 a,b를 b와 a를 b로 나눈 나머지로 치환한다.
• b가 0이 될때까지 반복한다.
• a를 b로 나눈 나머지가 0이 되면, 그때 나눴던 수 b가 두 수의 최대공약수가 된다.

# 최소공배수를 구하는 함수를 만든다.

• 최소공배수는 두 수를 곱한 값을 최대공약수로 나눈 값이다.

 

 

 

---

   추가내용   

# math.lcm(a, b)은 파이썬 3.9 버전부터 사용이 가능하다.