최대공약수와 최소공배수

최대공약수 (GCD : greatest common divisor)

유클리드의최대공약수 알고리즘

1. 두 개의 정수 u, v를 입력받는다.

2. v가 u보다 크면 값을 교환한다.

3. u에는 u-v의 값을 저장한다.

4. u가 0이면 v가 최대공약수.

   u가 0이 아니면 2로 돌아간다.

하지만 이 방법은 u와 v의 차가 크면 성능이 떨어지기때문에 다른 방법을 씁니다.

1. 두 개의 정수 u, v를 입력받는다.

2. v가 0이면 u가 최대공약수.

   0이 아니면 u에 u%v를 대입하고 u와v의 값을 교환한다.

3. 2로 돌아간다.

함수

int gcd(int u, int v)//최대공약수 { return (v==0)? u : gcd(v, u%v); }

재귀함수로 간단히 구현할 수 있습니다.

삼항연산자를 처음보는 어린이들은 책을 다시한번 보세요.

최소공배수 (LCM : lowest[least] common multiple)

1. 두 개의 정수 u, v를 입력받는다.

2. u*v를 u와v의 최대공약수로 나눈다.

헙헙, 저도 방금배웠어요. 고등수학은 참 재밌군뇨.

함수

int lcm(int u, int v)//최소공배수 { return u * v / gcd(u, v); }

참 쉽죠?

int gcd(int u, int v)//최대공약수 { return (v==0)? u : gcd(v, u%v); } int lcm(int u, int v)//최소공배수 { return u * v / gcd(u, v); } main() { int u, v; printf("두 개의 정수 입력\n>"); scanf("%d %d",&u, &v); printf("최대공약수 : %d\n", gcd(u,v)); printf("최소공배수 : %d", lcm(u,v)); }

첫 모의고사.