[5/25] 2609 (최대공약수와 최소공배수)

문제

내 코드

a, b = map(int, input().split())
if (a < b):
    a, b = b, a
for i in range(1, b+1):
    if (a % i == 0 and b % i == 0):
        maxx = i
minn = int((a * b) / maxx)
print(maxx, minn)

풀이

1. a와 b를 비교해 큰 수를 a로 지정한다.
2. for문을 사용하여, 약수를 maxx라고 지정한다. 결국 가장 큰 약수가 저장된다.
3. 최소공배수 구하는 공식은 '두 수의 합 / 최대공약수' 이다.

효율적인 코드

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

def gcd(a, b) :
    if b==0:
        return a
    else :
        return gcd(b,a%b)

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

print(gcd(a,b))
print(lcm(a,b))

피드백

• 최대공약수는 재귀함수와 유클리드 호제법을 이용하면 간단하다.

배운 것

• 재귀함수 로직