웹개발 및 최신 테크 소식을 전하는 블로그, 웹이즈프리
수학에 나오는 유클리드 호제법을 사용하여 최대공약수를 구하는 방법을 알아봅니다.
유클리드 호제법은 두 개의 정수 중 큰 수를 작은 수에 나눕니다. 이때 나머지를 가지고 다시 나웠던 수(작은 수)에 다시 나눕니다. 그러면 나머지가 나오는데 이 나머지가 0이 나올때 까지 계속해서 이전의 나머지에 나누게됩니다. 0이 나오게 되는 몫이 바로 두 수의 최대공약수가 됩니다. 이를 순서대로 나타내면 다음과 같습니다.
# 유클리스 호제법을 사용한 최대공약수 구하기
만약 두 수가 54, 76이라면 아래의 절차에 따릅니다.
그럼 위 방법이 맞는지 확인해보겠습니다.
54의 약수 - 1 2 3 6 9 18 27 54
76의 약수 - 1 2 4 19 38 76
같은 약수는 2뿐이므로 유클리드 호제법에 의한 방법과 정확히 일치합니다.
# 유클리드 호제법을 구하는 알고리즘
자바스크립트를 사용하여 구현해보도록 하겠습니다. 먼저 소스코드입니다.
아래는 실제 위 코드를 적용하여 만들어본 코드입니다. 아래 예제는 a, b 직접 입력해 테스트하는 것이 가능합니다. 직접 눌러보세요!
유클리드 호제법은 두 개의 정수 중 큰 수를 작은 수에 나눕니다. 이때 나머지를 가지고 다시 나웠던 수(작은 수)에 다시 나눕니다. 그러면 나머지가 나오는데 이 나머지가 0이 나올때 까지 계속해서 이전의 나머지에 나누게됩니다. 0이 나오게 되는 몫이 바로 두 수의 최대공약수가 됩니다. 이를 순서대로 나타내면 다음과 같습니다.
# 유클리스 호제법을 사용한 최대공약수 구하기
만약 두 수가 54, 76이라면 아래의 절차에 따릅니다.- a, b 두 수 중에서 큰 수인 76을 54로 나누기
- 이때 나머지 22로 54를 나누기
- 나머지 11로 22를 나누기
- 계산하면 몫이 2 나머지는 0이므로 최대 공약수는 2임
그럼 위 방법이 맞는지 확인해보겠습니다.
54의 약수 - 1 2 3 6 9 18 27 54
76의 약수 - 1 2 4 19 38 76
같은 약수는 2뿐이므로 유클리드 호제법에 의한 방법과 정확히 일치합니다.
# 유클리드 호제법을 구하는 알고리즘
자바스크립트를 사용하여 구현해보도록 하겠습니다. 먼저 소스코드입니다.<script>
function getGCD(a, b) {
if (a < b) {
c = a; a = b; b = c;
}
var restVal = getRest(a, b);
if (restVal === 0) {
alert(b);
}
else {
getGCD(b, restVal);
}
function getRest(a, b) {
return a % b;
}
}
</script>
위 코드를 잠시 설명하면 나머지가 0이되면 값을 return하고 그렇지 않은 경우 재귀함수를 계속해서 실행합니다. 그리고 a<b인 경우 ... 즉 b가 더 큰 경우에는 값의 위치를 바꾸는 코드가 맨 위의 if에 존재합니다.function getGCD(a, b) {
if (a < b) {
c = a; a = b; b = c;
}
var restVal = getRest(a, b);
if (restVal === 0) {
alert(b);
}
else {
getGCD(b, restVal);
}
function getRest(a, b) {
return a % b;
}
}
</script>
아래는 실제 위 코드를 적용하여 만들어본 코드입니다. 아래 예제는 a, b 직접 입력해 테스트하는 것이 가능합니다. 직접 눌러보세요!
아래의 글도 찾고 계시지 않나요?
