공부 기록

2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 예제 입력 출력 24 18 6 72 알고리즘 유클리드 호제법을 사용하여 해결하였다. [알고리즘] 최대공약수와 최소공배수 구하기, 유클리드 호제법 유클리드 호제법 최대공약수 GCD와 최소공배수를 구하는 방..

유클리드 호제법 최대공약수 GCD와 최소공배수를 구하는 방법 a,b ∈ ℤ 이고, r = a mod b (a를 b로 나눈 나머지)라고 가정하면 r 은 (0 ≤ r < b)이고 a ≥ b 이다. 그러면 이때 a와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같아지고 이는 다음과 같다. GCD(a, b) = GCD(b, r) 예시 1. a = 64, b = 42 일 경우 GCD(64, 42)일 때 r = 22이고 GCD(64, 42) = GCD(42, 22)이다. GCD(42, 22)를 보면 r = 20 이고 GCD(42, 22) = GCD(22, 20)이다. GCD(22, 20)을 보면 r = 2 이고 GCD(22, 20) = GCD(20, 2)이다. GC..