[TIL] 유클리드 호제법 Euclidean algorithm

유클리드 호제법 Euclidean algorithm

2개의 자연수의 최대공약수를 구하는 알고리즘 
호제법 - 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘 

 

유클리드 호제법 진행 순서

1. 두 수 중 큰 수를 작은 수로 나눈다

2. 나머지가 0이면 작은 수가 최대 공약수가 된다

3. 나머지가 0이 아니면 작은 수가 큰 수가 되고, 나머지가 작은 수가 되어

    다시 큰 수를 작은 수로 나눈다 

 

유클리드 호제법 특징

1. 시간 복잡도 O(log(min(a, b))) - 두 수의 크기에 비례하여 알고리즘의 수행 시간이 결정된다 

2. 재귀적으로 구현도 가능하다 ( gcd(a, b) -> gcd(b, a % b) )

+ 최대공약수 성질 중에 gcd(a, 0) = a 라는 성질도 있다, 즉, 어떤 수와 0의 최대공약수는 그 수 자체 

유클리드 호제법 Python 코드

a, b = map(int, input().split()) // a, b 입력 받기

// 유클리드 호제법 함수 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a 

print(gcd(a, b))

 

유클리드 호제법 C언어 코드

#include <stdio.h>

// 유클리드 호제법 함수 
int gcd(int a, int b) {
    while (b != 0) { // b 가 0 이 아닐 때까지 반복 
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a; // 최대공약수 반환 
}

int main() {
    int a, b; 
    // a, b 입력 받기 
    scanf("%d %d", &a, &b);
    
    // 최대공약수 출력 
    printf("%d\n", gcd(a, b));
    return 0; // 프로그램 종료 
}