유클리드 호제 법이란.(위키백과의 말을 가지고왔다.)
유클리드 호제법(- 互除法, 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); // 재귀함수, 유클리드 호제법 공식
}
'C' 카테고리의 다른 글
c언어 2의n승의 결과 출력하기 (0) | 2014.04.29 |
---|---|
c언어 입력한 돈으로 잔돈이 남지않게 물건 구입하기 (6) | 2014.04.28 |
c언어 사용자가 원하는 단부터 원하는 단까지 구구단 출력하기 (0) | 2014.04.28 |
c언어 10진수 정수 입력 받아 16진수와 8진수로 출력하기 (0) | 2014.04.28 |
c언어 재귀함수(순환함수) 이용하여 입력받은 숫자 차례로 출력하기 (2) | 2014.04.28 |