C언어 195제] 2004년 한국정보올림피아드 지역본선 중등/고등부 1번 최대공약수와 최소공배수

출처 : 반크_백제역사 유적지구와 이스탐블 역사지구

 

문제]

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1 
24 18
예제 출력 1 
6
72

출처 : 백준_2609번

 

참고 알고리즘 : 유클리드 호제법

참고풀이]

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

//유클리드 호제법 사용
//최대공약수 구하기
int GCD(int a, int b)
{
   return (b == 0) ? a : GCD(b, a % b);
}

//최소공배수 구하기
int LCM(int a, int b)
{
   int gcd = GCD(a, b);
   return gcd * (a / gcd) * (b / gcd);
}

int main()
{
   //두개의 자연수를 입력받는다.
   int x, y;
   scanf("%d%d", &x, &y);
   if ((x > 0 && x < 10000) && (y > 0 && y < 10000))
   {
      //최대공약수 결과출력
      printf("%d\n", GCD(x, y));
      //최대공배수 결과출력
      printf("%d", LCM(x, y));
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 가을