[BOJ] 백준 1934 최소공배수

[BOJ] 백준 1934 최소공배수

문제 링크 : https://www.acmicpc.net/problem/1934




이 문제는 말 그대로 최소공배수를 출력하면 되는 문제 입니다.
저는 최소공배수를 구하기 위해 무한루프 아래서 나눠보려는 수가  2,3,5,7 또는 2,3,5,7을 제외한 소수일 경우 이 수가 A,B를 나누었을때 나머지가 0인지 판단하여 최소공배수를 구했습니다.
보통 일반적인 최소공배수 구하는 법은 유클리드 호제법을 사용합니다.
유클리드 호제법이란, 큰 수와 작은 수 두개가 있을 때(A,B) 큰수%작은수의 값을 작은 수가 가지고, 큰 수는 작은수를 가지는 것을 반복 합니다. 여기서 마지막으로 %연산을 해서 나온 값이 최대공약수이고, 큰수와 작은수를 곱한 후 최대공약수로 나누면 최소공배수를 구할 수 있습니다.


유클리드 호제법으로 푼 코드 :

#include 
using namespace std;

long func(int a, int b) {
 int big, small;
 if (a > b) {
  big = a; small = b;
 }
 else {
  big = b; small = a;
 }
 while (1) {
  // 큰수 / 작은수 나머지를 n에 저장.
  int n = big % small;
  // n이 0일경우 작은수를 반환
  if (n == 0) return small;
  // 큰수가 작은수 역할
  big = small;
  // 작은수는 n을 취함
  small = n;
 }
}

int main() {
 int t;
 cin >> t; cin.ignore();
 for (int i = 0; i < t; i++) {
  int a, b;
  cin >> a >> b;
  cin.ignore();
  // 최소공배수는 A*B에 최대공약수를 곱해준 값.
  cout << (a * b)/func(a, b) << endl;
 }
}

소수를 이용하여 푼 코드 :

#include 
#include 
using namespace std;

long func(int a, int b) {
 vector  v;
 int cnt = 2;
 while (1) {

  // 소수 cnt로 a와b를 나누었을때 모두 나머지가 0 이면(공약수이면) v에 push.
  // push 후 다시 루프 돌기위해 cnt를 1로 셋팅.
  if ((cnt == 2 || cnt == 3 || cnt == 5 || cnt == 7) || (cnt % 2 != 0 && cnt % 3 != 0 && cnt % 5 != 0 && cnt % 7 != 0)) {
   if (a%cnt == 0 && b%cnt == 0) {
    a /= cnt;
    b /= cnt;
    v.push_back(cnt);
    cnt = 1;
   }
  }
  // 나누려는 소수가 a 혹은 b보다 크다면 탈출.
  if (cnt > a || cnt > b)break;
  cnt++;
 }
 long mul = 1;
 
 // 공약수 * 벌거벗은 a와b
 for (int i = 0; i < v.size(); i++) {
  mul *= v[i];
 }
 return mul * a * b;
}
int main() {
 int t;
 cin >> t; cin.ignore();
 for (int i = 0; i < t; i++) {
  int a, b;
  cin >> a >> b;
  cin.ignore();
  cout << func(a, b) << endl;
 }
}