[C] 백준 | 2609번 코드 - 최대공약수와 최소공배수

>문제

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

 

[입력]

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

> 핵심

최대공약수, 최소공배수 개념 알기

최소공배수는 a * b / gcd(a,b) 로 구할 수도 있다.

>풀이과정

최대공약수와 최소공배수. 대 1때 코딩 처음 배울때 만들어봤던 기억이 난다.

 

근데 문제를 보니 이거 중등부, 고등부 문제에 출제된 문제라고 한다.

난 중학생때 코딩이 뭔지도 모르고 C언어, 파이썬은 듣도보도 못했었는데.. 세상에 마상에

 

아무튼 풀고 나서 다른사람이 한 코드를 봤는데 "유클리드 호제법"이라는 알고리즘을 사용한 사람이 있었다.

나도 얼핏 알고리즘 기본서에서 봤던 것 같은데 그닥 관심있게 안보고 넘어간 것 같아서 이번에 다시 한번 공부했다.

 

유클리드 호제법?

-> 유클리드 호제법(Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 

 

나무위키 보니까 이게 인류 최초의 알고리즘이라고 한다. 

어떻게 기원전에 이걸 공식화할 생각을 했을까. 세상엔 천재들이 참 많다.

 

그리고 최소공배수는 두 자연수 곱에 최대공약수를 나눈것이라는 것도 이번에 다시 알아간다.

계산기만 뚜들기다 보니 이런건 지나고보면 금세 다 까먹는다. 이번에 다시 배우면 됐지 뭐. 

 

>깨달은점

코딩 안하면 중고등학생한테도 뒤쳐질지 모른다. 열심히 하자

 

>코드

1, 반복문

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int gcd(int a, int b)
{
	int num = 1, min, gcd = 1;
	min = a < b ? a : b;

	while (num <= min)
	{
		if (a % num == 0 && b % num == 0)
			gcd = num;
		num += 1;
	}

	return gcd;
}
 
int main()
{
	int a, b;

	scanf("%d %d", &a, &b);
	
	printf("%d %d\n", gcd(a, b), (a * b) / gcd(a, b));

	return 0;
}

2. 유클리드 호제법

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int e_gcd(int a, int b)
{
	if (b == 0)
		return a;
	else
		return e_gcd(b, a % b);
}

int main()
{
	int a, b, tmp;

	scanf("%d %d", &a, &b);

	if (a < b) {
		tmp = b;
		b = a;
		a = tmp;
	}

	printf("%d\n%d\n", e_gcd(a, b), (a * b) / e_gcd(a, b));

	return 0;
}