유클리드

[GCD 알고리즘] Euclidean Algorithm

1. 유클리드 알고리즘이란? Euclidean Algorithm (유클리드 호제법이라고도 합니다)은 두 수의 GCD(Greatest Common Divisor 최대공약수)를 구하는 알고리즘입니다. 2. 원리 STEP 1: 두 자연수 A, B가 있을때 A > B라 가정 STEP 2: A를 B로 나눈 나머지를 C라 가정. STEP 3: C가 0이면 B는 GCD STEP 4: C가 0이 아니면 B값을 A에 대입하고 C값을 B에 대입해 STEP 2부터 반복. A = 12 B = 18 A와 B를 나눈 나머지C는 12 B 가 0이 아니므로 B = A, C = B 대입 A = 18 B = 12 A와 B를 나눈 나머지C는 6 B 가 0이 아니므로 B = A, C = B 대입 A = 12 B = 6 A와 B를 나눈 나머..