[백준_python] 최대공약수와 최소공배수 || 2609 (유클리드 호제법)

www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

유클리드 호제법

a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. (b가 0이 될 때까지 반복)

gcd(24, 18) = gcd(18, 6) = gcd(6, 0)

최소공배수는 a*b/최대공약수 라고 한다.

---

a, b = map(int, input().split(' '))
a_max = []
b_max = []
for i in range(1, a+1):
    if a % i == 0:
        a_max.append(i)
for i in range(1, b+1):
    if b % i == 0:
        b_max.append(i)

max_ = []
for i in a_max:
    if i in b_max:
        max_.append(i)
print(max(max_)) ### 최대공약수

i = 1
x = max(a, b)
y = min(a, b)
while True:
    z = x * i
    if z % y == 0:
        print(z)  ###최대공배수
        break
    i += 1

일단 이 코드는,, 유클리드 호제법을 모르고 무작정 짜게 된 코드이다.
하나하나 나눠주면서 약수를 찾아주고 서로 같은 약수 중에 가장 큰 수를 찾아 최대공약수를 구해주었다.
또, 큰 수(a)를 하나씩 곱해줘가며 b와 나눠떨어지는 경우를 찾아 최소공배수를 구해주었다.

---

a, b = map(int, input().split(' '))
x, y = a, b
while b != 0:
    r = a%b
    a, b = b, r
print(a)
print(x*y//a)

b가 0이 될 때까지 나머지를 구해주면서 최대공약수를 구해주고, 최소공배수를 계산해준다..!
가장 간단하게 정리된 코드인 것 같다.

 
다음에 최대공약수, 최소공배수가 나오는 부분이 나오게 된다면 유클리드 호제법을 꼭 써먹자악!