[Prime Number] 유클리드 호제법 (소수 찾기)

최대 공약수를 구하는 방법 중의 하나이다. 호제법은 두수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

개요

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어떨어진다.

따라서, 최대공약수는 21이다.

상기한 1071과 1029에 대한 예시를 위와 같은 표현으로 적어보면,

처럼 쓸 수 있다.

 

정리

\(a,b\in {\mathbb {Z}}\)이고, \({\displaystyle a}\) 를 \({\displaystyle b}\) 로 나눈 나머지가 \({\displaystyle r}\) 이라고 하자. (여기서 \({\displaystyle a\geq b}\) 이고, \({\displaystyle r}\) 은 \({\displaystyle 0\leq r<b}\) 인 정수.) \(a\)와 \({\displaystyle b}\)의 최대공약수를 \({\displaystyle \left(a,b\right)}\) 라고 하면, 다음이 성립한다.

$${\displaystyle \left(a,b\right)=\left(b,r\right).}$$

 

증명

 

구현

아래에서는 유클리드 호제법은 코드로 표현한 것으로, 약간의 차이는 있지만 방식은 동일하다.

✅ 재귀

def gcd(m,n):
    if m < n:  # a ≥ b 상태를 유지하기 위해 대소 비교를 하여 b가 더 크다면 swap 한다.
        m, n = n, m
    if n == 0:  # 나머지가 0이면 그때의 m이 최대공약수
        return m
    if m % n == 0:  # 큰수%작은수 == 0 인것이니 작은수가 최대공약수
        return n
    else:  # 위 조건에 맞지 않으면 다음 호출로
        return gcd(n, m % n)  # 공식

 

✅ 반복문

def gcd(m,n):
    while n != 0:
       m, n = n, m%n
    return m

def gcd(m,n):
    while n != 0:
        if m < n:
            m, n = n, m
        if n == 0:
            return m
        if m % n == 0:
            return n
        else:
            m, n = n, m%n