유클리드 호제법 (최대공약수), 최소공배수

유클리드 호제법

---

의미: 최초의 알고리즘

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. (출처:wikipedia)

 

최대공약수 구하기

1. a,b 각각의 약수를 구해 공통되는 약수 중 가장 큰 값 찾기

2. 유클리드 호제법

숫자 a,b가 존재할 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대공약수가 같음.

따라서, 계속해서 a를 b로 나누어 b를 a에, 나눈 나머지를 b에 대입시켜 b가 0이 될 때까지 반복하면 남는 a값이 최대 공약수가 된다!

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

 

---

 

최소공배수

서로 다른 수 a,b의 배수중에서 공통되는 배수 중 가장 작은 값.

최소공배수는 a,b의 곱을 a,b의 최대 공약수로 나누면 나오게 됨!

def gcd(a,b): #최대공약수
    while b>0:
        a,b = b,a%b
    return a
def lcm(a,b): #최소공배수
    return int(a*b/gcd(a,b))