유클리드 호제법 : 기원전 300년경 기하학자 유클리드가 주장하여 그의 이름을 딴 공식으로 알려져 있다.
두 자연수 A,B에 대하여 A를 B로 나누었을 때 몫을 Q, 나머지를 R이라고 하면(A = BQ+R)
A,B의 최대공약수는 B,R의 최대공약수와 같다.
<증명> A,B 둘의 최대공약수 G
A = aG, B = bG (a,b는 서로소)
(A = BQ+R, B = bG 이므로)
bGQ+R = aG
=> R = (a - bQ)G
--------------------------
A = aG
B = bG
R = (a-bQ)G
그러므로 A,B의 최대공약수와 B,R의 최대공약수는 G로 서로 같다.
========================================================================
#include <stdio.h>
unsigned int gcd(unsigned int valuer1, unsigned int value2);
unsigned int lcm(unsigned int value1, unsigned int value2);
int main()
{
unsigned int value1, value2;
printf("자연수 2개를 입력하시오 : ");
scanf("%d %d", &value1, &value2);
printf("최대공약수 : %d\n", gcd(value1, value2));
printf("최소공배수 : %d\n", lcm(value1, value2));
return 0;
}
int lcm(int value1, int value2)
{
int temp;
temp = gcd(number1, number2);
return (number1/temp)*number2;
}
======================================================================
위의 소스는 우선 돌아가는 것 같지만 약점이 있다.
입력값을 전혀 체크하지 않는다는 것! 만약 자연수를 입력하지 않는다면 문제가 발생할 가능성이 크다.
0 0을 입력한다면? 만약 수를 입력하지 않고 문자를 입력해 버린다면?
간단히 오류체크를 추가해서 main을 바꿔보자.
int main()
{
unsigned int value1, value2;
do{
printf("자연수 2개를 입력하시오 : ");
scanf("%d %d", &value1, &value2);
}while(value1 <= 0 || value2 <= 0);
printf("최대공약수 : %d\n", gcd(value1, value2));
printf("최소공배수 : %d\n", lcm(value1, value2));
return 0;
}
간단히 do-while을 사용해서 자연수가 아닌 정수(0,음수)는 걸러주도록 했다.
숫자 이외의 값이 입력되는 경우는 찾아보기 쉽게 다른 글로 다시 써야겠다.
'Programming > C언어우려먹기' 카테고리의 다른 글
| 64bit 에서 int, long 사용 (0) | 2016.01.15 |
|---|---|
| 예외처리 scanf에서 이상한 값이 입력되었을 때. (4) | 2008.05.29 |
| factorial (재귀호출, 반복문) (0) | 2008.05.01 |
| 정렬 - 삽입정렬(Insert Sort), 힙정렬(Heap Sort), 쉘정렬(Shell Sort) (0) | 2008.04.27 |
| 정렬 - 버블정렬(bubble sort), 선택정렬(selection sort), 퀵정렬(quick sort) (0) | 2008.04.27 |
| source C 완전제곱수 판별 (2) | 2008.03.19 |
| C언어에서 사용되는 연산자들(사실 C,C++,JAVA등 다양한 언어에서 공통적으로 사용된다.) (0) | 2008.03.10 |
| 무지간단한 주사위 통계 (0) | 2008.03.03 |
| 2진수로 표현하기 (0) | 2008.02.28 |
