최대공약수 알고리즘, 유클리드의 호제법 +최소공배수 구하기

1. 유클리드 호제법이란 두 자연수의 최대공약수를 구하는 알고리즘 중 하나 유클리드의 저서 《기하학원본》에 기재되어 있는 최대공약수를 구하는 방법 호제법 또는 연제법 이라고 한다 사용되는 성질 a를 b로 나눈 나머지 = c 이면 a, b의 최대공약수는 b, c의 최대공약수와 같다 알고리즘 두 자연수 또는 다항식 a,b의 최대공약수를 구하는 데 있어, 자연수일 때는 a > b, 다항식일 때는 a의 차수가 b의 차수 이상이라 하고, 다음과 같이 나눗셈을 실행한다 b를 c로 나눈 나머지 = c' 를 구하고 c'를 d로 나눈 나머지 = ... 위 과정을 반복하여 나머지가 0이 되었을 때의 '나누는 수'가 a와 b의 최대공약수이다. 2. 예시 78696과 19332의 최대공약수 구하기 78696＝19332×4＋1..