최대공약수(GCD)_Euclidean, 최소공배수(LCM)
최대공약수(Greatest Common Divisor) 최대공약수란, 두 수의 공통된 약수들 중 가장 작은 수이다. 예를 들어, 20과 12의 약수는 다음과 같고 공통된 약수 중 가장 큰 수는 4이다. 20 : 1, 2, 4, 5, 10, 20 12 : 1, 2, 3, 4, 6, 12 두 수의 최대 공약수를 구하는 가장 원초적인 방법은 두 수의 약수를 모두 구하고, 이중 for문으로 공통인 약수를 탐색하면서 최댓값을 찾는 것이다. #include #include using namespace std; vector getDivisor(int n) { vector v; for (int i=1; i*i=0; i--) { if (v[i] == n/v[i]) continue; v.push_back(n/v[i]); ..
2022. 2. 15.