[ C001 ] - 최대공약수와 최소공배수

[설명]

 

임의의 두 정수를 입력 받아 유클리드 호제법을 이용하여, 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

 

[처리방법과 기준]

 

입력될 두 숫자를 x, y라하고 x < y 임을 가정합니다. x를 m에, y를 n에 저장하여(m은 분자, n은 분모를 의미) 다음 반복에 의해 최대 공약수와 최소 공배수를 계산합니다.

반복	m % n을 계산
	그 값이 0이면 n은 최대 공약수(반복 벗어남)
	그렇지 않으면 m에 n을 기억, 나머지 값을 n에 저장

 
이때n은 최대 공약수이며 최소 공배수는n*(x/n)*(y/n)으로 계산합니다.

 

 

[문제 분석]

 

구분	처리할 내용
입력	임의의 두 정수
처리	반복처리에 의해 최대 공약수를 계산, 최대 공약수로 최소 공배수를 계산
출력	최대 공약수, 최소 공배수

[입력 예]

첫 번째 숫자 입력 : 27

두 번째 숫자 입력 : 36

 

 

[출력 예]

최대 공약수 : 9

최소 공배수 : 108

/**     임의의 두 정수를 입력 받아 유클리드 호제법을 이용하여,     최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. */   #include <stdio.h>   int gcd( int, int ); int recursion( int, int );   int main() {     int a, b, g;       printf("[gcd] first number : ");     scanf("%d", &a);     printf("[gcd] second number : ");     scanf("%d", &b);     g = gcd(a, b);       printf("gcd = %d\n", g);                 // 최대 공약수 = (a * b) / 최소 공배수     printf("lcm = %d\n", (a * b) / g);    // 최소 공배수 = (a * b) / 최대 공약수       printf("[recursion] first number : ");     scanf("%d", &a);     printf("[recursion] second number : ");     scanf("%d", &b);     g = recursion(a, b);       printf("gcd = %d\n", g);                 // 최대 공약수 = (a * b) / 최소 공배수     printf("lcm = %d\n", (a * b) / g);    // 최소 공배수 = (a * b) / 최대 공약수       return 0; }   // % 연산을 이용한 유클리드 호제법으로 최대 공약수를 구하는 함수 int gcd( int a, int b ) {     int tmp;       while( b )     {         tmp = a;         a = b;         b = tmp % b;     }       return a; }   // 위의 함수를 개량하여 재귀적인 방법으로 최대 공약수를 구하는 함수 int recursion( int a, int b ) {     if ( a % b == 0 )         return b;     else         return recursion( b, a % b ); }