개념
<script>
/*
[최대공약수와 유클리드 호제법]
- 두 수의 최대공약수를 구하는 가장 효율적인 방법 중 하나가
바로 유클리드 호제법 입니다.
[유클리드 호제법의 원리]
- 두 자연수 A, B(A > B)가 있을 때,
A를 B로 나눈 나머지를 r이라고 하면,
A와 B의 최대공약수는 B와 r의 최대공약수와 같습니다.
[예시]
A = 106, B = 16인 경우
(1) 106 ÷ 16 = 6 ... 10 → 106과 16의 최대공약수 = 16과 10의 최대공약수
(2) 16 ÷ 10 = 1 ... 6 → 16과 10의 최대공약수 = 10과 6의 최대공약수
(3) 10 ÷ 6 = 1 ... 4 → 10과 6의 최대공악수 = 6과 4의 최대공약수
(4) 6 ÷ 4 = 1 ... 2 → 6과 4의 최대공약수 = 4와 2의 최대공약수
(5) 4 ÷ 2 = 2 ... 0 → 나머지가 0이므로 최대공약수는 2
- 이렇듯 나머지가 0이 될 때까지 반복하면,
마지막에 남는 B(또는 A)가 바로 최대공약수가 됩니다.
*/
let x = 106;
let y = 16;
// 두 수 중 큰 수를 x로 설정
if(x < y) {
let temp = x;
x = y;
y = temp;
}
// 유클리드 호제법 반복
while(y != 0) {
let temp = x % y;
x = y;
y = temp;
document.write(temp, " ", x , " ", y, "<br>");
}
document.write(x);
</script>
HTML
복사