본문 바로가기
공부/개발노트

[C/C++] 유클리드의 최대공약수 알고리즘

반응형



유클리드의 최대 공약수 알고리즘입니다.


알고리즘 문제

Euclid(a, b)

입력: 정수 a, b; 단 >= b >= 0

출력: 최대공약수(a, b)

if(b=0) return a

return Euclid(b, a mod b) 


위 조건을 만족하는 함수를 짜서 출력을 해야됩니다.


int gcdSubtract(int x, int y){
int subTemp, min, max;
if (x > y) { max = x; min = y; }
else { max = y; min = x; }
subTemp = max - min;
if (min != 0)
gcdSubtract(subTemp, min);
else
return max;
}
view raw dp hosted with ❤ by GitHub

우선 b가 클 경우 a와 b를 바꾸어줘야됩니다.

Euclid(b, a mod b)에 대한 것이죠.


int gcdModulus(int x, int y){
if (y != 0)
gcdModulus(y, x%y);
else
return x;
}
view raw dp hosted with ❤ by GitHub


조건이 만족했다면 위 함수를 호출하게됩니다.


그리고 메인함수에서 출력을 하게됩니다.


int main(void)
{
int gcdValue, num1, num2;
std::cout << "첫번째 수를 입력하시오: ";
std::cin >> num1;
std::cout << "두번째 수를 입력하시오: ";
std::cin >> num2;
//gcdValue = gcdModulus(num1, num2);
gcdValue = gcdSubtract(num1, num2);
std::cout << num1;
std::cout << "와";
std::cout << num2;
std::cout << "의 최대공약수는 ";
std::cout << gcdValue;
std::cout << "이다.";
return 0;
}
view raw dp hosted with ❤ by GitHub

감사합니다.

도움이 되셨으면 공감과 감사의 덧글 부탁드립니다.

반응형