[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; }
댓글
댓글 쓰기