사전지식

약수

12와 28의 약수는 ?

12의 약수 => 1 2 3 4 6 12

28의 약수 => 1 2 4 7 14 28

서로소

공약수가 1밖에 없는 두수를 서로소 관계에 있다고 한다.

예를들어, 17과 8은 서로소 관계에 있다. 공약수가 1밖에 없기 때문이다.

최대공약수

두 수의 공약수중 가장 큰것.

12와 28의 최대공약수는 4이다. 2와 4둘중에 4가 더 크기 때문이다.

최대공약수 구하는 방법

첫번째(노가다)

12의 약수와 28의 약수를 구한다음에 공통된것을 찾고(공약수), 그중에 가장 큰것(최대공약수)을 찾으면 된다.직관적이지만, 유클리드 호제법보다 속도가 느리다는 단점이 있다.

두번째(유클리드호제법)

유클리드 호제법이란?

A,B의 최대공약수를 G라고 할때(A > B)
[28과 1의 최대공약수를 4라고 할때(A > B)]


A = a * G, B = b * G(a, b는 서로소)로 나타낼 수 있습니다.
[28 = 7 * 4, 12 = 3 * 4 (7과 3은 서로소)로 나타낼 수 있습니다.]


A = q * B + r 에 A = a * G, B = b * G를 대입하면[r 은 A를 B로 나눈 나머지이다]

a * G = b * q * G + R
[7 * 4 = 3 * 2 * 4 + 4]

다시 정리하면


R = G(a – b * q) 인데
[4 = 4(7 – 3 * 2) 인데]


a – b * q와 b * G는 서로소 이기 때문에(왜냐하면, a,b가 서로소이므로)
B와 r의 최대공약수도 G가 된다.
(근데 왜,,, a,b가 서로소라고 해서 a-b*q 와 b*G가 서로소라는거지?)


요약하자면, A와 B의 최대공약수가 B와 R(A를 B로 나눈 나머지)의 최대공약수와 같다.

유클리드 호제법으로 최대공약수 찾기

198 과 120의 최대공약수

198 = 120 * 1 + 78 ( A = B * q + R )

198 과 120의 최대공약수120과 78의 최대공약수 와 같기 때문에 120과 78의 최대공약수를 구해보자

120 = 78 * 1 + 42

120과 78의 최대공약수78과 42의 최대공약수와 같기 때문에 78과 42의 최대공약수를 구해보자

78 = 42 * 1 + 36

78과 42의 최대공약수42와 36의 최대공약수와 같기 때문에 42와 36의 최대공약수를 구해보자

42 = 36 * 1 + 6

42와 36의 최대공약수36과 6의 최대공약수와 같기 때문에 36과 6의 최대공약수를 구해보자

36 = 6 * 6 + 0

이제 나머지가 0이 되었기 때문에, 36과 6의 최대공약수는 6이 된다(자기 자신으로 바로 나누어 떨어지니까!)

즉, 198과 120의 최대공약수A와 B의 최대공약수가 B와 R(A를 B로 나눈 나머지)의 최대공약수와 같다는 규칙에 의해서, 쭉쭉쭉 재귀적으로 해봤을때 36과 6의 최대공약수와 같고, 답은 6이된다.

코드로 표현

def gcd(a, b) :
    # 큰걸 앞쪽에 놓자
    if (b > a) :
        temp = a
        a = b
        b = temp

    # 나머지가 0이되면 끝나는거다.
    # 나머지가 b에 들어가니까, b가 0보다 클때까지만 나누기를 계속한다
    while b > 0 :
        r = a % b
        a = b # a자리에 b가 들어가고
        b = r # b자리에 r(나머지)가 들어간다
    
    # 마지막에 나누는수(b)가 a에 들어갔으니까, a를 리턴해준다
    return a

print(gcd(198, 120))

# 6 출력

출처

  1. https://mathbees2.blogspot.com/2014/09/4_24.html