유클리드 호제법(Euclidean Algorithm)

두 수의 최대공약수(GCD)를 구하는 알고리즘으로, 큰 수를 작은 수로 나누는 과정을 반복하여 최대공약수를 효율적으로 구하는 방법입니다.

 

📌 유클리드 호제법 원리

1. 두 수 a와 b가 있을 때, a>b라고 가정합니다.
2. a를 b로 나눈 나머지를 구합니다. (즉, r=a mod  b)
3. 나머지 r이 0이면, b가 최대공약수(GCD)입니다.
4. 나머지 r이 0이 아니면, a를 b로, b를 r로 바꾸고 2번 과정을 반복합니다.

✅ 예제 1: 24와 18의 GCD 구하기

📌 계산 과정

1. 24 mod  18=6 → 나머지 6 (24를 18로 나눈 나머지)
2. 18mod  6=0 → 나머지 0 (18을 6으로 나눈 나머지)
3. 나머지가 0이므로 최대공약수는 6입니다.

Java

public static int gcd(int a, int b) {         while (b != 0) {             int temp = b;             b = a % b;             a = temp;         }         return a;     }

 

🔍 작동 방식

1. 첫 번째 반복:
   • a=24,b=18 일 때,
   • a mod  b=24 mod  18=6 (즉, 24를 18로 나눈 나머지 6)
   • 이제 b를 6으로 바꾸고, a를 18로 바꿔서 다시 반복합니다.
2. 두 번째 반복:
   • a=18,b=6 일 때,
   • a mod  b=18 mod  6=0 (즉, 18을 6으로 나눈 나머지 0)
   • 나머지가 0이 되었으므로, 현재 b=6이 최대공약수(GCD)입니다.

최소공배수(LCM)는 두 수의 가장 작은 공통 배수를 의미합니다. 이를 구하는 공식은 최대공약수(GCD)를 이용하는 방법으로 쉽게 계산할 수 있습니다.

 

📌 최소공배수(LCM) 계산 공식

​

• **GCD(a, b)**는 두 수의 최대공약수입니다.
• **|a × b|**는 두 수의 곱입니다.
• LCM은 두 수의 곱을 최대공약수로 나누어 계산합니다.

✅ 왜 이 공식이 성립하는가?

• 두 수의 곱 a×b는 항상 두 수의 배수이지만, 그 중에서 가장 작은 공배수는 바로 두 수의 곱을 그들의 최대공약수로 나눈 값입니다.
• 이 공식은 두 수의 공배수들 중 가장 작은 값을 찾는 방법입니다.

두 수가 24와 18일 때, 그들의 LCM을 구해봅시다.

1. 최대공약수 (GCD): 

2. 최소공배수 (LCM):

 

public static int lcm(int a, int b) {             return a * (b / gcd(a, b)); // 오버플로우 방지 }