백준 2609 최대공약수와 최소공배수 (파이썬)

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

 

첫번째 제출 코드 (정답) 

import sys
A, B = map(int, sys.stdin.readline().split())
GCD = 0
LCM = 1
for i in range(1, min(A+1, B+1)):
    if A%i == 0 and B%i==0:
        GCD = i

SET = set()
for i in range(1, max(A+1, B+1)):
    if A%i == 0:
        SET.add(i)

DividendA = A
DividendB = B
LCMList = []
divider = 2
while DividendA and DividendB:
    if DividendA % divider == 0 and DividendB % divider == 0:
        DividendA //= divider
        DividendB //= divider
        LCMList.append(divider)
        divider = 2
        continue
    else:
        divider += 1
        if divider > DividendA or divider > DividendB:
            LCMList.append(DividendA)
            LCMList.append(DividendB)
            break

for mul in LCMList:
    LCM *= mul

print(GCD)
print(LCM)

 

초등학교로 잠시 돌아가 공약수와 공배수를 구하는 법을 다시 떠올렸습니다.

정답을 맞추고 이렇게 푸는 방법이 절대 아니라고 생각하여 정답을 제출하고 바로 정답을 검색 했습니다.

 

두번째 제출

import sys
def gcd(a, b):
    while b > 0:
        mod = a % b # 나머지
        # 유클리드 호제법
        #GCD(a,b) = GCD(b, mod)
        a, b = b, mod
    return a

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

A, B = map(int, sys.stdin.readline().split())
GCD = gcd(A,B)
print(GCD)
print(lcm(A,B, GCD))

유클리드 호제법으로 최대 공약수, 최소 공배수를 빠르게 찾을 수 있었습니다.

최대 공배수는 두 수를 곱해서 최대 공약수를 나눠주는 것도 오늘 다시 배우고 갑니다