c언어 2609번 최대공약수와 최소공배수 (백준)

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

#include <stdio.h>
#define min(a, b) (a<b) ? a : b //두 수 중 작은 수 구하기

int main(void)
{
    int n1, n2; //두 수 입력받을 변수
    scanf("%d%d", &n1, &n2); //입력받음
    int small = min(n1, n2); //두 수 중 작은 수 구하기
    
    int gcd = 1; //최대공약수를 담을 변수 (초기화는 1로)
    
    for(int i = 2; i<=small; i++) {//최대공약수의  최대값은 두 수중 작은 수 이다.
    	int count = 0; //소인수분해가 성공하면 1로 증가!
    	
    	if(n1 < i && n2 < i) break; //나눠질 수 보다, 나눌 수가 더 커지면, 더 이상 할 이유가 없다.
    	
    	if(n1%i==0 && n2%i==0) //i로 두수가 나눠진다면...
    	{
    		n1 /= i; //나눈다!
    		n2 /= i; //나눈다!
    		gcd = gcd * i; //그리고 i을 최대공약수에 곱한다!
    		count++; //소인수 분해 성공!
		}
		if(count > 0) i--; //소인수 분해 성공 시, 똑같은 값으로 한 번 더 나눠질 수 있으니, i--을 해줌으로써 i의 증가를 상쇄한다.
	}
	
	printf("%d %d", gcd, gcd*n1*n2); //gcd 출력 및 lcd = gcd*(gcd로 나누고 남은 (n1 * n2))
	return 0;
}

풀이

ex)

2 | 18 24
3 | 9 12
---------
3 4

gcd : 최대공약수 = 2 * 3
lcd : 최소공배수 = gcd * 3 * 4

그러므로 이 문제는 gcd만 구해도 된다!

1. 입력받은 두 수중 작은 수를 찾는다.

2. 2에서 부터 두 수중 작은 수까지 하나씩 입력받은 두 수와 나눠 떨어지는지를 확인하고, 나눠 떨어지면, 두 수를 나누면서, 최대공약수엔 곱을 한다. (나눠 떨어지면, 그 수로 다시 나눠 떨어지는지 확인해본다)

3. 반복문이 종료되면 최대공약수와, 최대공약수로 나눠진 n1, n2가 나오므로, 이 셋을 곱하여 최소공배수를 만든다.

4. 이를 출력한다.