[Algorithm] 유클리드 호제법 (정수론)

정수론 중 가장 많이 사용한다.

a, b가 주어졌을 때 이 둘의 최대 공약수를 구하는 문제

• a < b일 때, a와 b - a의 최대 공약수를 구하는 것과 같다.

예를 들어 8과 34의 최대 공약수를 구한다고 하면

8	34
8	26
8	18
8	10
8	2

8은 2로 나누어 떨어지니 2가 이 때의 최대 공약수이다.

뺄셈이 아닌 % 연산을 통해서 구하는 것이 가장 효율적이다.

최대 공약수(GCD)

나누어 떨어질 때의 작은 값을 구하면 그 때가 최대 공약수이다.

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

while a & b != 0:		# 나누어 떨어질 때까지 수를 줄여나간다.
    a, b = b, a % b

print(b)

최소 공배수(LCM)

GCD를 구할 줄 알면 LCM은 공짜이다.

LCM은 두 수를 곱하고 최대 공약수로 나누면 된다.

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

A, B = a,b
while a & b != 0:		# 나누어 떨어질 때까지 수를 줄여 나간다.
    a, b = b, a % b

print(A * B // b)