1/15
Loading...
📘최대공약수 = 가장 큰 공통 약수
GCD는 두 수를 모두 나눌 수 있는 가장 큰 수예요. 예시: 12와 18의 약수를 나열해볼까요? • 12의 약수: 1, 2, 3, 4, 6, 12 • 18의 약수: 1, 2, 3, 6, 9, 18 공통 약수: 1, 2, 3, 6 → 가장 큰 것은? 6! 따라서 GCD(12, 18) = 6
Loading...
GCD는 두 수를 모두 나눌 수 있는 가장 큰 수예요. 예시: 12와 18의 약수를 나열해볼까요? • 12의 약수: 1, 2, 3, 4, 6, 12 • 18의 약수: 1, 2, 3, 6, 9, 18 공통 약수: 1, 2, 3, 6 → 가장 큰 것은? 6! 따라서 GCD(12, 18) = 6
유클리드 호제법은 2000년 이상 된 알고리즘으로, 두 정수의 최대공약수(GCD)를 효율적으로 구합니다. 나눗셈의 나머지를 이용해 반복적으로 계산하며, GCD를 구하면 LCM도 쉽게 계산할 수 있습니다.