반응형
유클리드 호제법이란?
두개의 자연수의 최대공약수를 구하는 알고리즘이다.
알고리즘 방법으로는,
a>b일 때
a를 b로 나눈 나머지를 r이라고 할 때, a와b의 최대공약수는 b와 r의 최대공약수이다 .
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
보통 프로그래밍 언어에서의 유클리드 호제법 구현방법은 2가지가 있는데
첫 번째는 재귀적으로 나타내는 방법이다.
int gcd(int a, int b)
{
if(b==0) return a;
return gcd(b, a%b);
}
두 번째는 반복문의 방법이다.
int gcd(int a, int b){
int c;
while(b){
c = a%b;
a = b;
b = c;
}
return a;
}
출처:
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
반응형