[백준/C++] 14490번 백대열

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

문제

n, m이 :을 사이에 두고 주어질 때 두 수를 최대한으로 약분해서 출력한다. (1<=n,m<=100,000,000)

 

풀이

두 수의 최대 공약수 x를 구하여 n/x : m/x를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string s;
int n, m, x = 1;
vector<int> v;
//최대공약수로 나누기

int main() {
	cin >> s;
	for (int i = 0; i < s.length();i++) {
		if (s[i] == ':') {
			n = stoi(s.substr(0, i));
			m = stoi(s.substr(i + 1, s.length() - i));
		}
	}
	for (int i = 2; i <= n; i++) {
		if (n % i == 0) v.push_back(i);
	}
	for (int i = 2; i <= m; i++) {
		if (m % i == 0) {
			for (int j = 0; j < v.size(); j++) {
				if (i == v[j]) x = i;
			}
		}
	}

	cout << n / x << ':' << m / x;
}