최대공약수와 최소공배수 구하기 (feat. 유클리드 호제법)

시작하기 앞서 ...

유클리드 호제법의 코딩만 필요하다면 2.3.2로 가주시기 바랍니다.

1. 정의

배수: 어떤 수에 어떤 수를 곱한 수

숫자 a와 b가 있을 때 a가 b의 배수면 b는 a의 약수
에) 8은 4의 배수, 모든 정수는 1의 배수

약수: 어떤 수/식을 나누었을 때 나머지가 없이 떨어지는 수

예) 4은 8의 약수, 1은 모든 정수의 약수

최소공배수: 말 그대로 여러수 중에서 공통된 배수 중 가장 작은 수

예) 2와 3의 최소공배수는 6, 3과 9의 최소공배수는 9

최대공약수: 말 그대로 여러 수 중에서 공통된 약수 중 가장 큰 약수

'L자'로 최대공약수를 찾을 수도 있고 그냥 소인수분해하여 찾을 수도 있다

위 방법들도 괜찮긴 하지만 다루는 숫자가 정말 커질 수도 있는 코딩에서는 조금 더 효율적인, 무려 기원전 300년경에 유클리드에 의해 발견된 유클리드 호제법이다.

2. 유클리드 호제법

2.1 유클리드 호제법의 계산

숫자 a와 b가 각각 1112, 695일 때,

1112 % 695 = 417

695 % 417 = 278

417 % 278 = 139

278 % 139 = 0

유클리드 호제법의 한자식 표기는 互除이다. 서로(互) 나눈다(除)는 뜻으로, 그냥 더 큰 숭서 더 작은 수를 '빼'는 원리로 생각하는 것이 더 쉽다. 물론 실제로는 modulus(%) 연산자를 사용한다.

2.2 유클리드 호제법의 코딩화

2.3.1 pseudocode (의사코드)

a와 b를 입력받는다

b가 0보다 클때
	a와 b에 b와 a%b를 대입한다
a를 출력한다

2.3.2 code

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

while b > 0:
  a, b = b, a%b

print(a)