유클리드 호제법

 유클리드 호제법은 소인수분해를 하지 않고 2개의 자연수의 최대공약수를 구하는 알고리즘으로 큰 수들의 최대공약수를 구할 때 사용할 수 있다.

---

이해하기

 두 수 a, b가 있다고 하자. a와 b는 공약수 j의 배수이므로 아래와 같다.

A = 약수 j * a

B = 약수 j * b

 A를 B로 나누면 아래와 같다.

A = (B * x) + y

y = A - (B * x)

y = (j * a) - (j * b * x)

y = j * (a - b * x)

 즉, A를 B로 나눈 나머지 y는 A와 B의 공약수 j를 약수로 한다.

B = j * b

y = j * (a - b * x)

 위처럼 b와 y의 공약수는 j이다. 즉, b와 y의 최대공약수(i)는 j와 같거나 j보다 크다. (1)

B = 최대공약수 i * c

y = 최대공약수 i * d

 이를 A에 대입하면 아래와 같다.

B = 최대공약수 i * c

y = 최대공약수 i * d

A = (최대공약수 i * c * x) + 최대공약수 i * d

A = 최대공약수 i * (c * x + d)

 즉, i는 b와 y의 최대공약수도 되면서 A의 약수도 된다. 이때, A와 B의 공약수였던 j와 크기 비교를 해보면, j는 i와 같거나, i보다 커야 한다. (2)

 (1)과 (2) 조건이 동시에 성립해야 하므로 결국 i와 j는 같다.

A = i * a

B = i * b

A를 B로 나눈 나머지 y = i * d

---

코드로 나타내기

import sys

A, B = map(int, sys.stdin.readline().split())

num1, num2 = A, B

while num2 != 0:
  num1 = num1 % num2 # A를 B로 나눈 나머지(y)를 구하고
  num1, num2 = num2, num1
  # y를 제수로, B를 피제수로 바꾼다. (= B를 y로 나눈다.)
  # 이 때 나머지가 0이면 공약수를 찾았다는 의미이므로 반복문을 끝낸다.

# 최대공약수
print(num1)

# 최소공배수
print(A*B//num1)