백준 13241 파이썬 유클리드 호제법

백준 13241 - 최소공배수

문제

https://www.acmicpc.net/problem/13241

13241번: 최소공배수

13241번

답안 코드 :

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

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

A, B = map(int, input().split())

result = lcm(A, B)
print(result)

 

 

백준 / 문제 / 단계별로 풀어보기 / 15단계 약수, 배수와 소수 2

생각 :

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

# 유클리드 호제법을 사용하여 두 정수 a와 b의 최대공약수를 구합니다. 
# a를 b로 나눈 나머지를 새로운 a로, b를 이전의 a로 갱신하면서 반복합니다. 
# 나머지가 0이 될 때까지 반복하여 최대공약수를 찾습니다.

# def lcm(a, b):
#     return a * b // gcd(a, b)
# 최소공배수는 두 수의 곱을 최대공약수로 나눈 값

# 유클리드 호제법은 두 정수의 최대공약수(GCD)를 구하는 알고리즘 중 하나입니다. 
# 이 알고리즘은 기원전 300년경에 살았던 그리스 수학자 유클리드(Euclid)의 이름을 따서 명명되었습니다.

# 유클리드 호제법은 다음과 같이 작동합니다:

# 두 정수 a와 b가 주어집니다.
# a를 b로 나눈 나머지를 구합니다.
# 나머지가 0이 아니라면, b를 새로운 a로, 나머지를 새로운 b로 설정하고 2단계를 반복합니다.
# 나머지가 0이 되면, 이때의 b가 최대공약수(GCD)입니다.
# 간단한 예시를 통해 이해해보겠습니다. 두 수 48과 18의 최대공약수를 구하는 경우:

# 48을 18로 나눈 나머지는 12입니다. (48 % 18 = 12)
# 이제 a를 18로, b를 12로 설정합니다.
# 18을 12로 나눈 나머지는 6입니다. (18 % 12 = 6)
# 다시 a를 12로, b를 6으로 설정합니다.
# 12를 6으로 나눈 나머지는 0입니다. (12 % 6 = 0)
# 나머지가 0이므로, 이때의 b인 6이 최대공약수입니다.

# 따라서, 48과 18의 최대공약수는 6이 됩니다. 
# 유클리드 호제법은 이처럼 나머지가 0이 될 때까지 반복하여 
# 최대공약수를 찾는 간단하면서도 효과적인 알고리즘입니다.