c언어 재귀함수를 이용하여 유클리드호제법으로 두수의 최대공약수 구하기

유클리드 호제 법이란.(위키백과의 말을 가지고왔다.)

유클리드 호제법(- 互除法, Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 

재귀함수란?

#include<stdio.h>

#pragma warning(disable:4996)

int result(int n1, int n2);

int main(void)

{

int num1, num2;

printf("첫번째 정수 입력 : ");

scanf("%d", &num1);

printf("두번째 정수 입력 : ");

scanf("%d", &num2);

if (num1 < num2) // 큰수를 앞으로 작은수를 뒤로

printf("최대공약수는 %d 입니다.\n", result(num2, num1));

else

printf("최대공약수는 %d 입니다.\n", result(num1, num2));

return 0;

}

int result(int n1, int n2)// (int 큰값, int 작은값)

{

if (n2 == 0) // 작은값이 0일 경우, 나머지가 0일경우

return n1;

return result(n2, n1%n2); // 재귀함수, 유클리드 호제법 공식

}