백준 2609번 최대공약수와 최소공배수 c

이 문제는 두 자연수를 입력받아 최대공약수와 최소공배수를 출력하는 문제입니다.

 

#include <stdio.h>

int main() {
  int a, b, max, min, more;
  scanf("%d %d", &a, &b);

 

먼저 입력받을 두 자연수를 a, b라고 하고, 최대공약수를 max, 최소공배수를 min이라고 선언했습니다. more에는 a, b중에 더 큰 자연수를 대입할 것입니다.

그리고 a와 b를 입력받습니다.

 

  if(a > b){
    more = a;
  }
  else if(b > a){
    more = b;
  }

조건문을 이용해서 a와 b중에 더 큰 수를 more라고 합니다.

 

  for(int i = 1; i <= more; i++){
    if(a % i == 0 && b % i == 0){
      max = i; 
    }
  }

for문을 만들어 i로 더 큰수 자기자신이 될 때까지 a와 b를 나눕니다. 그래서 만약 두 수를 나눴을 때 모두 나머지가 0이라 i는 a와 b의 공약수일 것이고, 최대공약수를 그때의 i라고 대입합니다. 그래서 반복문이 끝날 때는 max는 두 수의 최대공약수입니다.

 

  min = (a/max)*(b/max)*max;

  printf("%d\n%d", max, min);

  return 0;
  
}

최소공배수를 구하는 방법은 수학에서 두 수를 각각 소인수분해하여 서로에게 없는 약수들을 곱해주면 최소공배수가 되는 것과 같은 원리로 두 자연수를 각각 두 수의 최대공약수로 나눈 값을 곱하고, 거기에 최대공약수를 한번 더 곱해주면 최소공배수를 구할 수 있습니다.

 

그리고 최대공약수와 최소공배수를 줄바꿈을 사이에 두고 출력하면 프로그램이 종료됩니다.

 

 

최대공약수를 구하는 데에는 별로 어려움이 없었는데 최소공배수를 구할 때  어떻게 해야 할 지 오래 고민했습니다. 유클리드 알고리즘을 사용해서 최소공배수를 구하는 경우가 많았는데, 코드가 조금 길기도 하고 이해하기도 어려워서 중학교 때 배웠던 소인수분해를 생각했습니다. 그래서 두 수를 각각 최대공약수로 나누고 최대공약수를 거기에 곱해주면 서로 공통이 아닌 약수들만 곱해진다는 것을 알았습니다. 이것을 이용하니 코드 한 줄로 최소공배수를 구할 수 있었습니다!