백준 알고리즘 문제 풀이 c/c++ -2609-

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

#include <stdio.h>

int main() {

  int arrA[100];
  int lengthA = 0;
  
  int arrB[100];
  int lengthB = 0;
  
  int LCM = 0; //최소공배수
  int GCD = 0; //최대공약수
  
  int A, B;
  scanf("%d %d", &A, &B);
  
  for(int i = 1; i <= A; i++){
    if(A % i == 0){
      arrA[lengthA] = i;
      lengthA++;
    }
  }
  
  for(int i = 1; i <= B; i++){
    if(B % i == 0){
      arrB[lengthB] = i;
      lengthB++;
    }
  }
  
  if(A > B){
    for(int i = 0; i < lengthB; i++){
      for(int j = 0; j < lengthA; j++){
        if(arrB[i] == arrA[j]){
          GCD = arrB[i];
        }
      }
    }
  }
  else if(B > A){
      for(int i = 0; i < lengthA; i++){
      for(int j = 0; j < lengthB; j++){
        if(arrA[i] == arrB[j]){
          GCD = arrA[i];
        }
      }
    }
  }
  else{
    GCD = A;
  }
  
  LCM = A * B / GCD;
  
  printf("%d\n", GCD);
  printf("%d\n", LCM);
  
  // A * B = LCM * GCD;

  return 0;
}

추후에 찾아보니 유클리드 호제법을 이용하면 훨씬 간단히 최대공약수/최소공배수 문제를 해결할 수 있었다

유클리드 호제법을 이용한 풀이도 올려보도록 하겠다