정올 1002 : 최대공약수, 최소공배수 응용
** 두 수의 곱 = 두 수의 최대공약수 * 최소공배수 유클리드 호제법 이용 조건: A>B 두 수 A와 B의 최대공약수 = B와 r(A를 B로 나눈 나머지)의 최대공약수 즉, GCD(A,B) = GCD(B,r) ex> GCD(30,18) = GCD(18,12) = GCD(12,6) = GCD(6,0) 두개의 숫자만 주어진 상황과 비슷한 형식으로 진행하면 된다. 예를 들어 두 개의 수 A와 B의 최대공약수를 D라고 하면, 세 개의 수 A,B,C의 최대공약수는 D와 C의 최대공약수와 같다. 아래는 재귀함수를 이용하여 구현해보았다. 최소공배수를 구하는 경우도 같은 방법으로 진행된다. 두 수 A,B가 주어졌을 때, A와 B의 곱 = A와 B의 최대공약수 * A와 B의 최소공배수 이다. 즉, lcm(A,B) = ..
2020. 4. 27.
정올 1658 : 최대공약수, 최소공배수 (+유클리드 호제법)
방법 1: 처음부터 확인해가면서 약수를 구함 -> 숫자가 커지면 시간이 오래걸린다. #include // 최대공약수 int gcd_get(int x, int y) { int res=0; for (int i = 1; i GCD(30,18) = GCD(18,12) = GCD(12,6) = GCD(6,0) #include // 최대공약수 int gcd_get(int x, int y) { if (y == 0)return x; return gcd_get(y, x % y); } int main() { int a, b; scanf("%d %d", &a, &b); int gcd = gcd_get(a, b); int lcm = (a * b) / gcd; printf("%d\n", gcd); printf("%d\n", l..
2020. 4. 27.
