[BJ] 최대공약수와 최소공배수

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

 

import math

def solution():
    a,b = map(int, input().split())
    
    #최대 공약수
    gcd_value = math.gcd(a,b)
    
    #최소 공배수
    lcm_value = (a*b) // gcd_value
    
    print(gcd_value)
    print(lcm_value)

1. 최대공약수 (GCD): 두 수의 최대공약수는 두 수가 나누어 떨어지는 가장 큰 수입니다. 이를 구하는 효율적인 알고리즘으로 유클리드 알고리즘을 사용할 수 있습니다. 두 수 a와 b에 대해, gcd(a, b)는 다음과 같이 구할 수 있습니다:
   • gcd(a, b) = gcd(b, a % b)
   • 이때, a % b는 a를 b로 나눈 나머지입니다.
   • 만약 b == 0이면 gcd(a, b)는 a입니다.
2. 최소공배수 (LCM): 두 수의 최소공배수는 두 수의 곱을 그들의 최대공약수로 나눈 값입니다. 즉,
   • lcm(a, b) = (a * b) / gcd(a, b) 입니다.

알고리즘

1. gcd(a, b)를 구합니다.
2. lcm(a, b)를 구하기 위해서 lcm(a, b) = (a * b) / gcd(a, b)를 계산합니다.