[파이썬] 최대공약수와 최소공배수

최대공약수 GCD : Greatest Common Divisor

두 수 이상의 공통인 약수 중 최대인 것

12의 약수 : 1, 2, 3, 4, 6, 12
6의 약수 : 1, 2, 3, 6
12와 6의 공통인 약수 : 1, 2, 3, 6
12와 6의 최대공약수 : 6

 

최소공배수 LCM : Least Common Multiple

두 수 이상의 공통인 배수 중 최소인 것

5의 배수 : 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, ...
15의 배수 : 15, 30, 45, 60, ...
5와 15의 공통인 배수 : 15, 30, 60, ...
5와 15의 최소공배수 : 15

 

최대공약수 & 최소공배수 구하기

유클리드 호제법

x, y 의 최대공약수는 y와 x%y의 최대공약수와 같음을 이용하는 방법

x와 y를 나눈 나머지가 0일 때까지 x%y를 수행

이때 나머지가 0이 될 때까지 x, y = y, (x%y) 으로 바꾸어 계산함

x와 y를 나눈 나머지가 0이 될 때, 이때의 y 값이 최대공약수

유클리드 호제법을 이용해 6과 12의 최대공약수 구하기
step1) x = 6, y = 12
-> x % y != 0 이므로 x, y = y, (x%y) 수행 
step2) x = 12, y = 6
-> x % y == 0 이므로 y 값이 최대공약수 
step3) 최대공약수 = 6

 

최대공약수를 통해 최소공배수 구하기

최소공배수는 x 와 y를 곱한 값을 최대공약수를 나눈 몫

6과 12의 최소공배수
x = 6, y = 12
최소공배수 = (x * y) // 최대공약수
-> (6 * 12) // 6 = 12

 

파이썬 코드1

def GCD(x,y):
    return y if x%y==0 else GCD(y,x%y)

def LCM(x,y):
    return (x*y)//GCD(x,y)

print(GCD(2,5)) # 1
print(LCM(2,5)) # 10

 

파이썬 코드2

math 모듈을 사용하는 방법

import math

print(math.gcd(2,5))
print(math.lcm(2,5))