최대공약수, 최소공배수

최대공약수

• 공약수 : 서로 다른 두 개 이상의 자연수에서 공통된 약수
• 최대공약수 : 공약수 중 가장 큰 수, 즉 서로 다른 두 개 이상의 자연수에서 얻은 공약수 중 가장 큰 수
• 최대공약수의 약수 = 공약수의 약수
• 서로소 : 공약수가 1뿐인 2개 이상의 자연수, 즉 최대공약수가 1

어떤 두 수의 최대공약수의 약수는 두 수의 약수에 포함된다.

12의 공약수 : 1, 2, 3, 4, 6, 12

18의 공약수 : 1, 2, 3, 6, 9, 18

최대공약수는 6 이고, 6의 약수는 1, 2, 3, 6 이다. 따라서 12와 18의 최대공약수는 6이고, 이 6의 약수는 12와 18의 약수이기도 하다.

소인수분해를 이용한 방법

기본적인 소인수 분해를 이용해 구하는 방법

def common_factor(x, y):
    '''소인수 분해를 이용한 공약수 구하기'''
    small = x
    if x > y:
        small = y

    numbers = [] # 소인수분해 결과 담는 리스트
    i = 2 # 2부터 나누기 시작
    
    while True:
        # i가 작은 수보다 커지면 더 이상 나눌 수 없어 끝낸다.
        if i > small: break
    
        # 공약수를 찾기위해 같이 나눠지는 수 구하기
        if x % i == 0 and y % i ==0:
            numbers.append(i) # 나눠지는 수는 결과에 담아두기
            # 다음 나눌 때는 현재 나눈 몫으로 나눠진 결괏값이 들어가야 한다.
            x /= i
            y /= i
            continue
        
        i += 1
        
    return numbers
    

def gcd(numbers):
    '''입력된 소인수 분해된 요소들을 이용해 
    최대 공약수 구하기'''
    answer = 1
    for i in numbers:
        answer *= i
        
    return answer


numbers = common_factor(85, 51)
print(numbers)
print(gcd(numbers))

유클리드 호제법(Euclidean Algorithm)을 이용한 방법

유클리트 호제법이란?

x를 어떤 수 y로 나눈 나머지 값을 r 이라고 했을 때,

x와 y의 최대공약수는 y 와 r의 최대공약수와 같다.

 

x = 85

y = 51

r = x % y = 85 % 51 = 34

x(85)와 y(51)의 최대공약수 = y(51)과 r(34)의 최대공약수

 

즉 y와 r의 최대공약수를 구하려면, 다시 y를 x에 넣고, y 자리에는 y % r의 나머지를 넣으면 된다.

 

이것을 반복하다보면 r이 0이 나오게 되는데, 이 때 r 즉 y 값이 0일 때 x가 최대공약수가 된다.

def gcd(x, y):
    while y:
        x, y = y, x % y

    return x

print(gcd(85, 51))

 

최소공배수

• 공배수 : 서로 다른 두 개 이상의 자연수에서 공통된 배수
• 최소공배수 : 공배수중 가장 작은 수, 즉 서로 다른 두 개 이상의 자연수에서 얻은 배수중 가장 작은 수
• 최소공배수의 배수 = 공배수의 배수

최대공약수를 이용한 방법

최대공약수를 찾은 다음 최대공약수로 나눈 몫을 모두 곱하면 된다.

def lcm(x, y):
    n = gcd(x, y)
    
    return (x // n) * (y // n) * n

print(lcm(85, 51)) # 255
print(lcm(24, 36)) # 72
print(lcm(60, 48)) # 240

유클리드 호제법을 이용한 방법

최대공약수를 이용한 방법을 축약한 방법

두 수를 곱한 값에 최대공약수로 나눠주면 최소공배수가 된다.

def lcm(x, y):
    '''최소 공배수는 입력된 x 와 y 의 값을 최대 공약수로 나눈 몫과 같다.'''
    return x * y // gcd(x, y)

print(lcm(85, 51)) # 255
print(lcm(24, 36)) # 72
print(lcm(60, 48)) # 240