[알고리즘, 원리] 유클리드 호제법

정의

a = bx+r 일 때

(a,b) = (b,r)

 

a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다. 이를 이용하여 반복하면 두 수의 최대공약수를 쉽게 구할 수 있다.

 

구현

파이썬 (Python)

def gcd(a,b):
    while b != 0:
        a, b = b, a%b
    return a

두 수에서 유클리드 호제법을 반복하여 최대공약수를 구하는 함수

 

def gcd(a, b):
    r = b % a
    if r == 0:
        return a
    return gcd(r, a)

재귀 함수를 이용한 구현

 

def gcd(*num_list):
    if len(num_list) == 1:
        return num_list[0]
    elif len(num_list) == 2:
        a, b = num_list[0], num_list[1]
        while b != 0:
            a, b = b, a%b
        return a
    else:
        return gcd(num_list[0], gcd(*num_list[1:]))

여러 수 이상일 경우 최대공약수를 구하는 함수. (a,b,c) = (a,(b,c))이기 때문에 재귀를 이용하여 반복해줌

 

자바스크립트 (Javascript)

function gcd(a,b){
    while(b != 0){
        var r = a%b;
        a = b;
        b = r;
    }
    return a
}

 

C, C++

int gcd(int a, int b)
{
    int r = a % b;
    if (r == 0) {
      return b;
    }
    return gcd(b, r);
}

 

원리 및 증명

a = bq + r

G = (a, b)

G` = (b, r)

라 가정하자. 그러면 서로소인 A, B에 대해

a = GA, b = GB

GA = GBq + r

 b=Gb, r=G(A-Bq)

G는 G`의 약수가 된다.

 

G` = mG

라 가정하면 서로소인 k,l에 대해

b = GB = G`k = Gmk

r = G(A-Bq) = G`l = Gml

양 변을 G로 나누면

B= mk

A-Bq = ml

정리하면

A = Bq+ ml = m(kq + l)

B = mk

m이 A와 B의 공약수가 된다. 하지만 A와 B는 서로소이므로 m=1, 따라서 G=G`

 

궁금한 내용이 있으면
화면 왼쪽 아래의 디스코드 아이콘을 누르면 실시간으로 답해드립니다.
(아이콘이 보이지 않는다면 에드 블록을 꺼주세요)

https://discord.link/pseudodeveloper

또 위 링크를 눌러 가짜 개발자 서버에 들어오시면
블로그의 새 글 알림을 받고
SSAFY, 부스트캠프, 포유드림, 우아한테크코스, 프로그래머스와 같은
국비 지원 교육 일정을 자동 알림 받을 수 있습니다.