유클리드 호제법

유클리드 호제법은 두 양의 정수의 최대공약수(GCD)를 구하는 고전 알고리즘입니다. 이 예제는 두 수가 같아질 때까지 큰 쪽에서 작은 쪽을 빼는 변형을 사용합니다.

이 변형은 다음 성질을 이용합니다.

• gcd(a, b) = gcd(a - b, b) (단, a > b)
• gcd(a, a) = a

코드

오ㅋ준ㅋ서ㅋ~준서!ㅋ
오ㅋ준ㅋ서ㅋ~준서!!ㅋ

준서야 !!@!! 또처먹냐?
  준서야 !ㅊ!! 맞냐?
    !~?!!~준서!ㅋ
  ㅋ 아니냐?
    !!~?!~준서!!ㅋ
  ㅋ
ㅋ

오준서!ㅋ

변수

변수	의미
!	첫 번째 수 (a)
!!	두 번째 수 (b)

동작 방식

1. 두 양의 정수 a, b를 입력받아 각각 !, !!에 저장합니다.
2. a와 b가 같지 않은 동안 다음을 반복합니다.
   • a > b이면 a에 a - b를 대입합니다.
   • 그 외의 경우 b에 b - a를 대입합니다.
3. 루프가 끝나면 두 변수의 값이 같아져 있으며, 이 값이 GCD입니다. !을 출력합니다.

실행 예시

입력 (a, b)	출력	의미
오 오오, 오 오오오오오오오오	오오오오오오	gcd(12, 18) = 6
오 오오오오오, 오 오?	오오오오오	gcd(15, 10) = 5
오오오오오오오, 오 오오오	오	gcd(7, 13) = 1

WARNING

• 이 알고리즘은 양의 정수에만 동작합니다. 0이나 음수를 입력하면 루프가 종료되지 않을 수 있습니다.
  
• 이 예제에서 사용된 빼기 기반 호제법은 두 수의 차이가 클수록 반복 횟수가 비례해 늘어납니다. gcd(1, 1000000)처럼 한 쪽이 매우 큰 경우 매우 느려질 수 있습니다.