[BOJ] 백준 2609 최대공약수와 최소공배수

[BOJ] 백준 2609 최대공약수와 최소공배수

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


이 문제는 잘 알려진 최대공약수와 최소공배수를 구하는 문제 입니다.
초등학교때 배워서 알고 있는 최대공약수, 최소공배수 구하는 방법 그대로 코딩을 하면 되는
문제 였습니다.
주의할 점으로, 두 수가 있을 때 나눠볼수 있는 수는 소수라는것 입니다.


소스 코드 :

#include 
#include 
using namespace std;

int main() {
 int a, b;
 cin >> a >> b; cin.ignore();
 vector v;
 while (true) {

  // 약수를 찾지 못했을 경우를 탐지할 flag 선언.
  bool flag = false;

  // 약수를 찾는 루프. i가 2,3,5,7로 나눠질 경우를 찾습니다.
  for (int i = 2; i <= 10000; i++) {
   if (i%2==0 || i%3 ==0 || i%5 == 0 || i%7 == 0) {
    if(i !=2 && i!=3 && i!=5 && i!=7)
     continue;
   }

   //  최소 약수를 찾았을 경우 a, b는 그 약수로 나누고 탐지 flag는 true,
   // 약수를 벡터에 넣어주고 루프 탈출.
   if (a%i == 0 && b%i == 0) {
    a /= i;
    b /= i;
    flag = true;
    v.push_back(i);
    break;
   }

  }

  // i가 10000이 될때까지 약수를 찾지 못했다면 탈출.
  if (!flag) break;
 }
 int mul = 1;

 // 찾은 약수들을 전부 곱해주는 루프. (최대공약수 도출)
 for (int i = 0; i < v.size(); i++) {
  mul *= v[i];
 }
 // 최대공약수 * a * b 는 최소공배수임.
 cout << mul << endl << mul * a*b << endl;
}